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);
    }
}

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;
}

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: 其餘的邊

應用

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.