广度优先搜素 -- 图的遍历

#include <iostream>
#include <algorithm>
using namespace std ;
const int INF = 0x3f3f3f3f ;
const int MAX =100 ;
int n  , m ;
int book[MAX]; // 用于标记 是否访问过book[i]  i 顶点
int que[MAX] ; // 队列
int map[MAX][MAX] ; // 用一个二维数组来存储图
void init()
{
  // 邻接矩阵存储图;
  int i ,j ;
  for(i=1 ;i<=n;i++)
  {
    for(j = 1 ; j<=n ;j++)
    {
      if(i==j)
      map[i][j] = 0 ;
      else
      map[i][j] = INF ;

    }
    
  }
  int a ,b ;
  for(i=1; i<=m;i++)
  {
    // 写入邻边
    cin>>a>>b ;
    map[a][b] = 1 ;
    map[b][a] = 1 ;
  }

  return ;
}
int main()
{
  int head = 1 ; // 对头
  int tail = 1 ; // 队尾
  int i ;
  cin>>n >>m ;
  init();
  que[tail] = 1; // 先把 1 这个顶点放入到队列中去 ;
  tail++;
  book[1] = 1; // 标记第一个顶点已经访问过了
  
  while(head<tail &&tail<=n)
  {
    int cur = que[head];// 每次都把对列的头赋给cur 作为当前顶点
    // 对 1 ~ n 依次遍历;
    for(i=1;i<=n ;i++)
    {
      if(map[cur][i]==1 && book[i]==0)
       // 如果cur节点 可以到达 i 节点 并且还没有访问过i
      {
        // 把它加入到队列中来
        que[tail] = i ;
        tail++ ;
        book[i] = 1 ; // 标记
        
      }
      
    }
    if(tail>n)
    {
      break;
    }
    head++; // 一定不要忘记
  }

  for(i=1;i<=n;i++)
  {
    cout<<que[i]<<" ";
  }

  return 0;
}

广度优先搜素的主要思想就是: 首先要以一个未被访问的顶点作为起始顶点,访问其相邻的顶点，然后对每一个相邻的顶点，再去访问他们相邻的未被访问的顶点，直到所有的顶点都被访问过;

 que      

        head                                                                                                                                     tail