广度优先遍历
广度优先遍历是非常常见和普遍的一种图的遍历方法了，，除了BFS还有DFS也就是深度优先遍历方法，我在我下一篇博客里面会写。
遍历过程
相信每个看这篇博客的人，都能看懂邻接链表存储图。 不懂的人，请先学下图的存储方法。在我的之前博客里。 传送门：图表示方法
然后我们假设有一个图如下：
节点1->3->NULL 节点2->NULL 节点3->2->4->NULL 节点4->1->2->NULL
这样我们已经知道这是一个什么图了。
假设我们从节点1开始遍历。 首先把节点1变成灰色，然后加入到队列(queue)中，然后把所有与节点1的点变成灰色同时加入到队列中。
输出并弹出队首元素节点1并把节点1的颜色变为黑色。
然后再把队首元素的相邻节点加入到队列中。然后继续输出并弹出队首元素依次类推。到队列空为止。
代码实现
下面是我写的代码实现，比较简单。
我有写一部分注释。
;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 GraphVertex OutDegree = 0;VList temp = NULL;for (int i = 1; i <= NumVertex; i++) {scanf(“%d”,&OutDegree); // input the out degree of vertexT[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<Vertex> Q;Q.push(start);VList temp = NULL;while (!Q.empty()) { //if queue is not empty, then the bfs is not overtemp = T[Q.front()].header; (T[temp->val].color == WHITE) {Q.push(temp->val); //push the white vertex to queueT[temp->val].color = GRAY; //change the color to gray}temp = temp->next;}printf(“%d “,Q.front()); //output the vertexT[Q.front()].color = BLACK; //then change colorQ.pop();}}int main(int argc, const char * argv[]) {Table T;InitTableEntry(1, T);BFS(1, T);return 0;}
上面的代码就是BFS了。其实还有很多其他实现方法。都可以。
在乎的是看风景的心情，旅行不会因为美丽的风景终止。
