图形的广度优先搜索(BFS)

广度优先搜索(BFS)遍历是一种算法，用于访问给定图的所有节点。在这种遍历算法中，选择了一个节点，然后一个接一个地访问所有相邻节点。完成所有相邻顶点后，它会进一步移动以检查另一个顶点并再次检查其相邻顶点。

要实现此算法，我们需要使用Queue数据结构。当所有相邻顶点完成时，所有相邻顶点都添加到队列中，从队列中删除一项，然后再次开始遍历该顶点。

有时在Graph中，我们可能会得到一些循环，因此我们将使用数组来标记何时访问节点或不访问节点。

输入输出

Input:
The Adjacency matrix of the graph.

     A B C D E F
   A 0 1 1 1 0 0
   B 1 0 0 1 1 0
   C 1 0 0 1 0 1
   D 1 1 1 0 1 1
   E 0 1 0 1 0 1
   F 0 0 1 1 1 0

Output:
BFS Traversal: B A D E C F

算法

bfs(vertices, start)

输入- 顶点列表和起始顶点。

输出-遍历所有节点（如果已连接图形）。

Begin
   define an empty queue que
   at first mark all nodes status as unvisited
   add the start vertex into the que

   while que is not empty, do
      delete item from que and set to u
      display the vertex u

      for all vertices 1 adjacent with u, do
         if vertices[i] is unvisited, then
            mark vertices[i] as temporarily visited
            add v into the queue
         mark
      done

      mark u as completely visited
   done
End

示例

#include<iostream>
#include<queue>
#define NODE 6
using namespace std;

typedef struct node {
   int val;
   int state;    //status
}node;

int graph[NODE][NODE] = {
   {0, 1, 1, 1, 0, 0},
   {1, 0, 0, 1, 1, 0},
   {1, 0, 0, 1, 0, 1},
   {1, 1, 1, 0, 1, 1},
   {0, 1, 0, 1, 0, 1},
   {0, 0, 1, 1, 1, 0}
};

void bfs(node *vert, node s) {
   node u;
   int i, j;
   queue<node> que;

   for(i = 0; i<NODE; i++) {
      vert[i].state = 0;    //not visited
   }

   vert[s.val].state = 1;   //visited
   que.push(s);            //insert starting node

   while(!que.empty()) {
      u = que.front();    //delete from queue and print
      que.pop();
      cout << char(u.val+'A') << " ";

      for(i = 0; i<NODE; i++) {
         if(graph[i][u.val]) {
            //当未访问该节点时
            if(vert[i].state == 0) {
               vert[i].state = 1;
               que.push(vert[i]);
            }    
         }
      }
      u.state = 2;   //completed for node u
   }
}

int main() {
   node vertices[NODE];
   node start;
   char s;

   for(int i = 0; i<NODE; i++) {
      vertices[i].val = i;
   }

   s = 'B';   //starting vertex B
   start.val = s-'A';
   cout << "BFS Traversal: ";
   bfs(vertices, start);
   cout << endl;
}

输出结果

BFS Traversal: B A D E C F