# 4.2 - Graph Traversal

拜訪Graph中的每個頂點一次:

1. **Depth First Search**
2. **Breadth First Search**

### DFS (Undirected Graph)

```
void DFS(int graph[NUM_NODES][NUM_NODES], int *visit, int start){
    //adjacency matrix(Graph以相鄰矩陣表示)
    printf("%d ", start);
    visit[start] = 1;
    for (int i = 0; i<NUM_NODES; i++){
        if (graph[start][i] == 1 && visit[i] == 0) //未曾拜訪過且是相鄰頂點
            DFS(graph, visit, i);
    }
}
```

<img src="/files/-LIiwHrEPtKusjIsvH-T" alt="" data-size="original">&#x20;

DFS: 0→1→3→7→4→5→2→6

並非唯一，除非規定頂點編號小的優先。

### BFS (Undirected Graph)

```
void BFS(int graph[NUM_NODES][NUM_NODES], int *visit, int start){
    queue *q = (queue *)malloc(sizeof(queue));
    create_queue(q, NUM_NODES); //建立空的queue
    visit[start] = 1;
    enqueue(q, start);
    while(!IsEmpty(q)){
        int next = dequeue(q);
        printf("%d ", next);
        for (int i = 0; i<NUM_NODES; i++){
            if (graph[next][i] == 1 && visit[i] == 0){ //未曾拜訪過且是相鄰頂點
                visit[i] = 1;
                enqueue(q, i);
            }
        }
    }
} 
```

BFS: 0→1→2→3→4→5→6→7

### BFS (Undirected Graph)(Algo)

可求頂點到各點的最短路徑長

```
typedef enum {
    white, //未拜訪的頂點
    gray,  //拜訪過，未結束的頂點
    black  //結束拜訪的頂點
}color_of_node;

struct vertex{
    color_of_node color;
    int u_distance; //起點到此頂點的距離
    int pi;  /此頂點的父點
};
```

```
void BFS(int graph[NUM_NODES][NUM_NODES], int start){
    //initialize
    queue *q = (queue *)malloc(sizeof(queue));
    create_queue(q, NUM_NODES);
    struct vertex node[NUM_NODES];
    for (int i = 0; i< NUM_NODES;i++){ //頂點參數初始化
        node[i].color = white;
        node[i].u_distance = 0;
        node[i].pi = -1;
    }
    //起點設置
    node[start].color = gray;
    node[start].u_distance = 0;
    node[start].pi = -1;
    //BFS
    enqueue(q, start);
    while(!IsEmpty(q)){
        int next = dequeue(q);
        printf("%d ", next);
        for (int i = 0; i<NUM_NODES; i++){
            if (graph[next][i] == 1 && node[i].color == white){
                node[i].color = gray;
                node[i].u_distance = node[next].u_distance+1;
                node[i].pi = next;
                enqueue(q, i);
            }
        }
        node[next].color = black; //結束拜訪
    }
}
```

### DFS (Directed Graph)(Algo)

```
void DFS(int graph[NUM_NODES][NUM_NODES]){
    //初始化
    struct vertex node[NUM_NODES];
    int time = 0;
    for (int i = 0; i< NUM_NODES;i++){
        node[i].color = white;
        node[i].discover_time = 0;
        node[i].finish_time = 0;
        node[i].pi = -1;
    }
    //拜訪每個頂點
    for (int i = 0; i< NUM_NODES;i++){
        if (node[i].color == white)
            DFS_VISIT(graph, node, i, time);
    }

}
```

```
void DFS_VISIT(int graph[6][6], struct vertex node[6], int u, int time){
    printf("%d ", u);
    time++;
    node[u].discover_time = time;
    node[u].color = gray;
    for (int i = 0; i<6;i++){ //從u去找下一個頂點
        if (node[i].color == white){
            node[i].pi = u;
            DFS_VISIT(graph, node, i, time);
        }
    }
    node[u].color = black;
    time++;
    node[u].finish_time = time;
}
```

<img src="/files/-LIjhDdyDhX_ddKlPWzx" alt="" data-size="original">&#x20;

DFS: 0→1→2→3→4→5

* Tree edge: 當v為white時，\<u, v>為Tree edge
* Back edge: 當v為gray時(v是u的祖先)，\<u, v>為Back edge
* Forward edge: 當v為black時(v是u的後代)，\<u, v>可能為Forward edge

  u的discover time必須小於v的discover time才成立
* Cross edge: 其餘的邊

<img src="/files/-LIjkhp2XhB2YMaHqYhj" alt="" data-size="original">&#x20;

### 應用

#### Is the undirected graph connected?

1. DFS/BFS
2. 檢查`visit[]`是否皆為True
   1. 是: connected
   2. 否: unconnected

#### Is there cycles in the graph?

判斷是否有back edge存在，有back edge則必有cycles。

```
if (node[v].color == gray) <u, v> is back edge.
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://garychang.gitbook.io/data-structure/4-graph/4.2-graph-traversal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.