算法學習 - 圖的廣度優先遍歷(BFS) (C++)

廣度優先遍歷

廣度優先遍歷是非常常見和普遍的一種圖的遍歷方法了，除了BFS還有DFS也就是深度優先遍歷方法，我在我下一篇博客裡面會寫。

遍歷過程

相信每個看這篇博客的人，都能看懂鄰接鏈表存儲圖。
不懂的人，請先學下圖的存儲方法。在我的之前博客裡。
傳送門：圖表示方法

然後我們假設有一個圖如下：

節點1->3->NULL
節點2->NULL
節點3->2->4->NULL
節點4->1->2->NULL

這樣我們已經知道這是一個什麼圖了。

假設我們從節點1開始遍歷。
首先把節點1變成灰色，然後加入到隊列(queue)中，然後把所有與節點1的點變成灰色同時加入到隊列中。

輸出並彈出隊首元素節點1並把節點1的顏色變為黑色。

然後再把隊首元素的相鄰節點加入到隊列中。然後繼續輸出並彈出隊首元素依次類推。到隊列空為止。

代碼實現

下面是我寫的代碼實現，比較簡單。

我有寫一部分注釋。

//
//  main.cpp
//  BFS
//
//  Created by Alps on 15/3/30.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include 
#include 

#ifndef Vertex
#define Vertex int
#endif

#ifndef NumVertex
#define NumVertex 4
#endif

#define WHITE 0
#define GRAY 1
#define BLACK 2

using namespace std;

struct node{
    int val;
    int weight;
    node* next;
    node(int v, int w): val(v), weight(w), next(NULL){}
};

typedef node* VList;

struct TableEntery{
    VList header;
    Vertex color;
};

typedef TableEntery Table[NumVertex+1];

void InitTableEntry(Vertex start, Table T){ //init the Graph
    Vertex OutDegree = 0;
    VList temp = NULL;

    for (int i = 1; i <= NumVertex; i++) {
        scanf("%d",&OutDegree); // input the out degree of vertex
        T[i].header = NULL;
        T[i].color = WHITE;
        for (int j = 0; j < OutDegree; j++) {
            temp = (VList)malloc(sizeof(struct node));
            scanf("%d %d",&temp->val, &temp->weight);
            temp->next = T[i].header;
            T[i].header = temp;
        }
    }

    T[start].color = GRAY; //init the start vertex color to gray
}

void BFS(Vertex start, Table T){
    queue Q;
    Q.push(start);
    VList temp = NULL;
    while (!Q.empty()) { //if queue is not empty, then the bfs is not over
        temp = T[Q.front()].header; //find the front of the queue
        while (temp) { //if the front vertex has next vertex
            if (T[temp->val].color == WHITE) {
                Q.push(temp->val); //push the white vertex to queue
                T[temp->val].color = GRAY; //change the color to gray
            }
            temp = temp->next;
        }
        printf("%d ",Q.front()); //output the vertex
        T[Q.front()].color = BLACK; //then change color
        Q.pop();
    }
}

int main(int argc, const char * argv[]) {
    Table T;
    InitTableEntry(1, T);
    BFS(1, T);
    return 0;
}

上面的代碼就是BFS了。其實還有很多其他實現方法。都可以。