> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/data-structure/4-graph/4.2-graph-traversal.md).

# 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.
```