题外话：在上一章我们介绍了一些关于连通域的基础概念，这一章我介绍一下上一章中关于种子填充算法的一些基础算法理解，便于之后更加透彻的理解。这章主要介绍广度优先搜索（BFS），深度优先搜索（DFS）算法。说实话，这两个算法在大二学数据结构时老师讲解过，但当时只是用来应付考试，并没有想到可以用到之后的比赛中，所以希望大家在学习一些知识时，可以将该知识点发散到一些自己感兴趣的地方，或许对此会有更深的影响。 
在介绍广度优先搜索（BFS），深度优先搜索（DFS）算法前首先介绍一下数据结构的图，具体的一些基础概念就不介绍了，感兴趣的同学可以看下我的另一篇文章：数据结构笔记-图。这里简单介绍一种图，无向图。

                                                      无向图

我们希望从图中的某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，对于这一过程我们就叫做图的遍历。

以上图为例，我们想要遍历从v0到v6的每一个顶点，且每一个顶点只能被访问一次。那么，我们需要怎么做到？简单来说，我们需要在遍历的过程中把每个访问过的顶点打上标记，用来避免我们多次访问而不知，具体的实现方法就是设置一个访问数组visited[n]，n是图中顶点的个数，数组初始化全部为0，每访问过一个顶点后设置为1。

对于图的遍历来说，我们需要科学的设计遍历方案，通常我们有两种遍历次序的方案，也就是我们今天所要讲的：广度优先搜索（BFS），深度优先搜索（DFS）算法。

广度优先遍历（BFS）：

图的广度优先遍历有些类似于树的层序遍历，我们将上面的无向图分一下层，将顶点v0放置在第一层，让与他有边的顶点v1、v2、v3为第二层，再让与v1、v2、v3有边的顶点v4、v5为第三层，最后将v6设置为第四层。

1.创建布尔类型的数组visited[n]，用来记录访问过的顶点，未访问的为FALSE，已访问的为                TRUE。                                                                                                                                             创建一个队列（队头出元素，队尾进元素），用来存放每一层的顶点；初始化图G。

2.初始化visited[n]，全部置为FALSE，此时队列中没有元素

3.从图中v0开始访问，将的visited[v0]数组的值设置为true，同时将v0入队。

4.只要队列不空，则重复如下操作：

    (1)队头顶点u出队。

    (2)依次检查u的所有邻接顶点w，若visited[w]的值为false，则访问w，并将visited[w]置为true，同时将w入队。

总结：BFS就是以v为起始点，由远及近依次访问和v有路径相通的顶点

BFS的伪代码： 

bool visted[MAX_NUM];    //定义bool类型访问数组
 
void BFS_Travel(Graph G){               //对图G进行广度优先遍历(防止图为非连通域)
   for(int i=0;i<G.vexnum;++i) 
     visted[i]=FALSE;                   //初始化访问数组
 
   InitQueue(Q);                        //初始化辅助队列
 
   for(i=0;i<G.vexnum;++i)            
     if(!visted[i])               //对每个连通分量调用一次BFS
       BFS(G,i);
}
 
void BFS(Graph G,int v){              //从顶点v开始访问
  visit(v);                           //访问初始顶点v
  visted[v]=TRUE;                     //设置为已访问
 
  Enqueue(Q,v);                       //顶点v入列Q
 
  while(!isEmpty(Q)){
  DeQueue(Q,v);                      //出列
  for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v))    //检测邻接点
   if(!visted[w]){          //找到未被访问的邻接点
     visit(w);              //访问顶点w
     visted[w]=TRUE;
 
     Enqueue(Q,v);
    }
  }
}

以上面的无向图为例我们讲解：

假设从v0开始访问，v0先入队。此时队列非空，取出对头元素v0，由于v2，v1，v3与v0连接且未被访问，依次访问这三个点，并将v2，v1，v3依次入队。此时队列非空，取出对头元素v2，并依次访问与v2连接且未被访问过的点v4，并入列。此时队列非空，访问与v1的未访问邻接点v1...........

深度优先遍历（DFS）：

深度优先遍历其实就是一个递归的过程，他类似于树的前序遍历。它从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。

下面我们以一张无向图为例：

 我们需要从顶点A开始遍历所有的图顶点并做上标记。首先我们从顶点A开始，做上表示走过的记号后，面前有两条路，通向B和F,我们给自己定一个原则，在没有碰到重复顶点的情况下，始终是向右手边走，于是走到了B顶点。整个行路过程，可参看图下图。此时发现有三条分支，分别通

向顶点C、I、G,右手通行原则，使得我们走到了C顶点。就这样，我们一直顺着右手通道走，一直走到F顶点。当我们依然选择右手通道走过去后，发现走回到顶点A了，因为在这里做了记号表示已经走过。此时我们退回到顶点F,走向从右数的第二条通道，到了G顶点，它有三条通道，发现B和D都已经是走过的，于是走到H,当我们面对通向H的两条通道D和E时，会发现都已经走过了。
此时我们是否已经遍历了所有顶点呢?没有。可能还有很多分支的顶点我们没有走到，所以我们按原路返回。在顶点H处,再无通道没走过，返回到G,也无未走过通道，返回到F,没有通道，返回到E,有一条通道通往H的通道，验证后也是走过的，再返回到顶点D,此时还有三条道未走过，一条条来，H走过了，G走过了，I,这是一个新顶点，没有标记，赶快记下来。继续返回，直到返回顶点A,确认你已经完成遍历任务，找到所有的9个顶点。

bool visted[MAX_NUM];    //定义bool类型访问数组
 
void DFS_Travel(Graph G){               
   for(int i=0;i<G.vexnum;++i) 
     visted[i]=FALSE;                  
 
   for(i=0;i<G.vexnum;++i)            
     if(!visted[i])               
       DFS(G,i);
}
 
void DFS(Graph G,int v){              
  visit(v);                           
  visted[v]=TRUE;                    
 
  for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))    //检测邻接点 w为v尚未访问的邻接点
   if(!visted[w]){          
      DFS(D,w);
  }
}