BFS

 1 #include<stdio.h>
 2 #include<queue>
 3 
 4 using namespace std;
 5 static const int N = 100;
 6 static const int INFTY = (1 << 21);
 7 
 8 int n, M[N][N];
 9 int d[N];
10 
11 void bfs(int s)
12 {
13     queue<int> q;
14     q.push(s);
15     for (int i = 0;i < n;i++ )        d[i] = INFTY;
16     d[s] = 0;                                //将第一个节点的距离定义为 0 
17     int u;
18     while( !q.empty() ) {                    //如果队列不为空 
19         u = q.front() ;    q.pop() ;            //将队首取出 
20         for ( int v = 0; v < n;v++ ){
21             if ( M[u][v] == 0 || d[v] != INFTY)    continue;        //M为领接矩阵判断是否连通，d判断是否已遍历过 
22             d[v] = d[u] + 1;                //d[u]为前一步的距离 
23             q.push(v);                         //将新的节点放入队列 
24         }
25     }
26 }