图的遍历的两种算法及其相关代码_遍历检测算法

深度优先遍历

深度优先遍历（Depth_First_Search），也有称为深度优先搜索，简称为DFS。

是一种用于遍历或搜索图的算法，其基本思想是从图的某个顶点开始，沿着一条路径尽可能深入地访问图中的顶点，直到到达一个没有未访问过的邻接顶点为止，然后返回并选择下一个未访问的顶点进行访问，重复这个过程，直到所有的顶点都被访问到。

深度优先遍历的主要步骤如下：
1. 从图中选择一个起始顶点作为当前顶点，并将其标记为已访问。
2. 访问当前顶点，并对其邻接顶点进行递归遍历。
3. 在访问邻接顶点之前，首先检查该邻接顶点是否已经被访问过，如果已经被访问过，则跳过该顶点。
4. 递归地对每个未被访问的邻接顶点进行深度优先遍历。

深度优先遍历可以使用递归或栈来实现。在递归实现中，递归函数会不断调用自身来遍历邻接顶点。在栈实现中，使用一个栈来存储需要遍历的顶点，从栈顶取出顶点进行访问，然后将其未访问的邻接顶点压入栈中，重复这个过程，直到栈为空。

深度优先遍历的特点是首先访问到达的顶点并沿着路径一直深入到不能再深入为止，然后返回并继续访问其他未被访问的顶点。因此，深度优先遍历可以很好地用于探索图的路径和连通性。它常用于解决与图相关的问题，如连通性、环路检测、拓扑排序等。

需要注意的是，在实际应用中，由于图可能包含环路，为了避免陷入无限循环，需要使用一个额外的数据结构来标记已经访问过的顶点，以确保每个顶点只被访问一次。

总结起来，深度优先遍历是一种以深度优先的方式遍历图的算法，通过递归或栈的方式访问顶点及其邻接顶点，用于发现路径和连通性。它对于解决与图相关的问题非常有用。

如果我们用的是邻接矩阵的方式，则代码如下：

/*  Boolean是布尔类型，其值是TRUE或FALSE  */
typedef  int  Boolean;    
/*  访问标志的数组  */
Boolean  visited[MAX];    
/*  邻接矩阵的深度优先递归算法  */
void  DFS(MGraph  G,  int  i)
{
int  j;
visited[i]  =  TRUE;
/*  打印顶点，也可以其他操作  */
printf("%c  ",  G.vexs[i]);        
for  (j  =  0;  j  <  G.numVertexes;  j++)
if  (G.arc[i][j]  ==  1  &&  !visited[j])
/*  对为访问的邻接顶点递归调用  */
DFS(G,  j);  
}
/*  邻接矩阵的深度遍历操作  */
void  DFSTraverse(MGraph  G)
{
int  i;
for  (i  =  0;  i  <  G.numVertexes;  i++)
/*  初始所有顶点状态都是未访问过状态  */
visited[i]  =  FALSE;     
for  (i  =  0;  i  <  G.numVertexes;  i++)
/*  对未访问过的顶点调用DFS，若是连通图，只会执行一次  */
if  (!visited[i])         
DFS(G,  i);
}

代码的执行过程，其实就是我们刚才迷宫找寻所有顶点的过程。
如果图结构是邻接表结构，其DFSTraverse函数的代码是几乎相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下。

/*  邻接表的深度优先递归算法  */
void  DFS(GraphAdjList  GL,  int  i)
{
EdgeNode  *p;
visited[i]  =  TRUE;
/*  打印顶点，也可以其他操作  */
printf("%c  ",  GL->adjList[i].data);  
p  =  GL->adjList[i].firstedge;
while  (p){if  (!visited[p->adjvex])
/*  对为访问的邻接顶点递归调用  */
DFS(GL,  p->adjvex);      
p  =  p->next;}}
/*  邻接表的深度遍历操作  */
void  DFSTraverse(GraphAdjList  GL)
{
int  i;
for  (i  =  0;  i  <  GL->numVertexes;  i++)
/*  初始所有顶点状态都是未访问过状态  */
visited[i]  =  FALSE;     
for  (i  =  0;  i  <  GL->numVertexes;  i++)
/*  对未访问过的顶点调用DFS，若是连通图，只会执行一次  */
if  (!visited[i])         
DFS(GL,  i);
}

对比两个不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
对于有向图而言，由于它只是对通道存在可行或不可行，算法上没有变化，是完全可以通用的。这里就不再详述了。

广度优先遍历
 

广度优先遍历（Breadth_First_Search），又称为广度优先搜索，简称BFS。

广度优先遍历用于遍历或搜索图中的所有顶点。它从一个起始顶点开始，首先访问该顶点，然后依次访问与起始顶点相邻的所有顶点，再依次访问与这些相邻顶点相邻的所有顶点，以此类推，直到图中所有顶点都被访问。

在广度优先遍历中，我们使用队列来实现。具体步骤如下：

1. 选取一个起始顶点作为当前顶点，将其入队，并标记为已访问。
2. 出队一个顶点，访问该顶点，并将其所有未访问的邻接顶点入队。
3. 重复步骤2，直到队列为空。

房间找钥匙：我们可以先看一遍所有的房间，可能会发现钥匙是不是放在很显眼的位置。如果没有找到，我们可以按照层级进行查找。首先查找与起始顶点A相邻的顶点B和F，然后再查找与B和F相邻的顶点C、I、G、E，再查找与这些顶点相邻的顶点D、H。通过层级遍历，我们可以逐层扩大查找的范围，直到找到为止。

有了这个讲解，我们来看代码就非常容易了。以下是邻接矩阵结构的广度优先遍历算法。

/*  邻接矩阵的广度遍历算法  */
void  BFSTraverse(MGraph  G)
{
int  i,  j;
Queue  Q;
for  (i  =  0;  i  <  G.numVertexes;  i++)
visited[i]  =  FALSE;
/*  初始化一辅助用的队列  */
InitQueue(&Q);            
/*  对每一个顶点做循环  */
for  (i  =  0;  i  <  G.numVertexes;  i++)          
     {
/*  若是未访问过就处理  */
if  (!visited[i])         
    {
/*  设置当前顶点访问过  */
visited[i]=TRUE;          
/*  打印顶点，也可以其他操作  */
printf("%c  ",  G.vexs[i]);            
/*  将此顶点入队列  */
EnQueue(&Q,i);            
/*  若当前队列不为空  */
while  (!QueueEmpty(Q))   
   {
/*  将队中元素出队列，赋值给i  *
/DeQueue(&Q,  &i);         
for  (j  =  0;  j  <  G.numVertexes;  j++)
 {
/*  判断其他顶点若与当前顶点存在边且未访问过  */
if  (G.arc[i][j]  ==  1  &&  !visited[j])
{
/*  将找到的此顶点标记为已访问  */
visited[j]=TRUE;          
/*  打印顶点  */
printf("%c  ",  G.vexs[j]);        
/*  将找到的此顶点入队列  */
EnQueue(&Q,j);            
}}}}}}
对于邻接表的广度优先遍历，代码与邻接矩阵差异不大，代码如下。
/*  邻接表的广度遍历算法  */
void  BFSTraverse(GraphAdjList  GL)
{
int  i;
EdgeNode  *p;
Queue  Q;
for  (i  =  0;  i  <  GL->numVertexes;  i++)
visited[i]  =  FALSE;
InitQueue(&Q);
for  (i  =  0;  i  <  GL->numVertexes;  i++)
{
 if  (!visited[i]){visited[i]  =  TRUE;
/*  打印顶点，也可以其他操作  */
printf("%c  ",  GL->adjList[i].data);  
EnQueue(&Q,  i);
while  (!QueueEmpty(Q)){DeQueue(&Q,  &i);
/*  找到当前顶点边表链表头指针  */
p  =  GL->adjList[i].firstedge;        
while  (p)
{
/*  若此顶点未被访问  */
if  (!visited[p->adjvex]) 
{
 visited[p->adjvex]  =  TRUE;
printf("%c  ",  GL->adjList[p->adjvex].data);
/*  将此顶点入队列  */
EnQueue(&Q,  p->adjvex);  
}
/*  指针指向下一个邻接点  */
p  =  p->next;            
}}}}}

广度优先遍历常用于解决许多与图相关的问题，如最短路径、连通性判断等。

对比图的深度优先遍历与广度优先遍历算法，你会发现，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点访问的顺序不同。可见两者在全图遍历上是没有优劣之分的，只是视不同的情况选择不同的算法。

不过如果图顶点和边非常多，不能在短时间内遍历完成，遍历的目的是为了寻找合适的顶点，那么选择哪种遍历就要仔细斟酌了。深度优先更适合目标比较明确，以找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

这里还要再多说几句，对于深度和广度而言，已经不是简单的算法实现问题，完全可以上升到方法论的角度。你求学是博览群书、不求甚解，还是深钻细研、鞭辟入里；你旅游是走马观花、蜻蜓点水，还是下马看花、深度体验；你交友是四海之内皆兄弟，还是人生得一知己足矣……其实都无对错之分，只视不同人的理解而有了不同的诠释。个人觉得深度和广度是既矛盾又统一的两个方面，偏颇都不可取，望大家慢慢体会。