無向圖 廣度優先遍歷 c語言實現

無向圖 廣度優先遍歷 c語言實現

這裡記錄一下無向圖的廣度優先遍歷，無向圖用鄰接表表示，使用的圖的示例圖如下，關於圖的表示可以參照博客：無向圖的表示：鄰接矩陣和鄰接表，這裡不再贅述，無向圖的表示的代碼被封裝到頭文件queue.h 中。
另外還涉及到C語言的隊列問題，可以參照博客：C 循環隊列實現，同樣不再贅述，循環隊列實現的代碼被封裝到頭文件graph_represent.h 中。

程序使用示例圖：

實現要點：
每個定點有三個狀態，-1,0,1，-1：表示未發現的節點；0：表示已經發現但是還沒有處理的節點；1：表示已經處理的節點。在遍歷過程中同樣保存了“樹邊（tree edge）”,樹邊表示在遍歷過程中經歷過的點。
程序框架如下：

代碼如下：

#include 
#include 
#include "queue.h"
#include "graph_represent.h"

void BFS(struct vNode** adj,int n,int s,int* parent){
    int* color = (int*)malloc(sizeof(int)*(n)); //-1:未發現，0:已發現，未處理, 1:已經處理
    int i;
    Queue* pending = createQue(n);  //創建隊列

    for(i=0;ivalue]==-1){
                color[w->value] = 0;
                add(pending,w->value);
                parent[w->value] = v;/**在這裡處理樹邊**/
            }
            w = w->next;
        }
        printf("%d ",v);/**在這裡處理節點**/
        color[v] = 1;
    }
    printf("\n");
}


void main(){

    //獲得默認圖,一共有7個節點
    int n = 7;
    struct vNode** adjVertics = default_wraper();
    int* parent = (int*)malloc(sizeof(int)*n);

    printf("\nbreadth first search:\n");
    BFS(adjVertics,n,2,parent);//從第二個節點開始遍歷
}

從第二個節點開始遍歷，輸出為：2 0 1 3 5 4 6