4.2 - Graph Traversal

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

Depth First Search
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?

DFS/BFS
檢查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.

Previous4.1 - Intro Next4.3 - Spanning Tree

Last updated 6 years ago

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

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

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; //結束拜訪 } }

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