DFS深度优先搜索遍历

悠悠 2021-11-22 11:14 397阅读 0赞

转载：[https://blog.csdn.net/qq\_38442065/article/details/81634282][https_blog.csdn.net_qq_38442065_article_details_81634282] 超简单详细

图的邻接表矩阵存储图，包含一位数组和指向节点的结构体，栈实现访问节点，递归实现dfs.

深度优先搜索(DFS, Depth First Search)是一个针对图和树的遍历算法。早在19世纪就被用于解决迷宫问题。

对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。   
![这里写图片描述][SouthEast]  
DFS的实现方式相比于BFS应该说大同小异，只是把queue换成了stack而已，stack具有后进先出LIFO(Last Input First Output)的特性，DFS的操作步骤如下：   
1、把起始点放入stack；   
2、重复下述3步骤，直到stack为空为止：

*  从stack中访问栈顶的点；
 *  找出与此点邻接的且尚未遍历的点，进行标记，然后全部放入stack中；
 *  如果此点没有尚未遍历的邻接点，则将此点从stack中弹出。

下面结合一个图(graph)的实例，说明DFS的工作过程和原理：   
（1）将起始节点1放入栈stack中，标记为已遍历。   
![这里写图片描述][SouthEast 1]  
（2）从stack中访问栈顶的节点1，找出与节点1邻接的节点，有2,9两个节点，我们可以选择其中任何一个，选择规则可以人为设定，这里假设按照节点数字顺序由小到大选择，选中的是2，标记为已遍历，然后放入stack中。   
![这里写图片描述][SouthEast 2]  
（3）从stack中取出栈顶的节点2，找出与节点2邻接的节点，有1,3,5三个节点，节点1已遍历过，排除；3,5中按照预定的规则选中的是3，标记为已遍历，然后放入stack中。   
![这里写图片描述][SouthEast 3]  
（4）从stack中取出栈顶的节点3，找出与节点3邻接的节点，有2,4两个节点，节点2已遍历过，排除；选中的是节点4，标记为已遍历，然后放入stack中。   
![这里写图片描述][SouthEast 4]  
（5）从stack中取出栈顶的节点4，找出与节点4邻接的节点，有3,5,6三个节点，节点3已遍历过，排除；选中的是节点5，标记为已遍历，然后放入stack中。   
![这里写图片描述][SouthEast 5]  
（6）从stack中取出栈顶的节点5，找出与节点5邻接的节点，有2,4两个节点，节点2,4都已遍历过，因此节点5没有尚未遍历的邻接点，则将此点从stack中弹出。   
![这里写图片描述][SouthEast 6]  
（7）当前stack栈顶的节点是4，找出与节点4邻接的节点，有3,5,6三个节点，节点3,5都已遍历过，排除；选中的是节点6，标记为已遍历，然后放入stack中。   
![这里写图片描述][SouthEast 7]  
（8）当前stack栈顶的节点是6，找出与节点6邻接的节点，有4,7,8三个节点，4已遍历，按照规则选中的是7，标记为已遍历，然后放入stack中。   
![这里写图片描述][SouthEast 8]  
（9）当前stack栈顶的节点是7，找出与节点7邻接的节点，只有节点6，已遍历过，因此没有尚未遍历的邻接点，将节点7从stack中弹出。   
![这里写图片描述][SouthEast 9]  
（10）当前stack栈顶的节点是6，找出与节点6邻接的节点，有节点7,8，7已遍历过，因此将节点8放入stack中。   
![这里写图片描述][SouthEast 10]  
（11）当前stack栈顶的节点是8，找出与节点8邻接的节点，有节点1,6,9，1,6已遍历过，因此将节点9放入stack中。   
![这里写图片描述][SouthEast 11]  
（12）当前stack栈顶的节点是9，没有尚未遍历的邻接点，将节点9弹出，依次类推，栈中剩余节点8,6,4,3,2,1都没有尚未遍历的邻接点，都将弹出，最后栈为空。   
（13）DFS遍历完成。

--------------------

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h6ZW5nd2VpMTMxMw_size_16_color_FFFFFF_t_70][]

**算法：**

int visited[maxSize];     //访问标志的数组
    
    /* V是起点的编号，visited[]是一个全局的数组，作为顶点的访问标记，初始时所有的元素均为0，0表示被访问过，即所有的元素都没有被访问过。因图中可能存在回路，当前经过的顶点在将来还可能再次经过，所以要对每一个顶点进行标记，以免重复访问。 */
    void DFS(AGraph *G,int V)
    {
         ArcNode *p ;    //图的顶点的搜索指针
         visited[v]=1;   //置已经访问
         printf("%d",v);   //输出访问过的顶点
         visited(v);      //函数visited()代表了一类访问顶点v的操作
         p=G->adjlist[v].firstarc;   //p指向顶点v的第一条边
         while(p != null){
               if(visited[p->adjvex]==0)     //若顶点未访问，则递归访问它
                      DFS(G,p->adjvex);
              p = p->nextarc;      //p指向顶点v的下一条边的终点
          }
    
    }

[https_blog.csdn.net_qq_38442065_article_details_81634282]: https://blog.csdn.net/qq_38442065/article/details/81634282
[SouthEast]: /images/20211122/62a0c4f9fe4d4cf8be760c65ab49cc94.png
[SouthEast 1]: /images/20211122/5561e9c7e9434f7a9bfc8914a74f4c54.png
[SouthEast 2]: /images/20211122/01c3e93cc68043b6b3966c528f47623d.png
[SouthEast 3]: /images/20211122/c8917f67332d4b94a7c620976a4ff9c2.png
[SouthEast 4]: /images/20211122/da18cfb0539a43b6b45fcf555e385308.png
[SouthEast 5]: /images/20211122/e0984ad43f234568beab067000c8a1d9.png
[SouthEast 6]: /images/20211122/6c1c39f8dc67471ea0755bd2f5a55420.png
[SouthEast 7]: /images/20211122/b42a089023fa446a99d527fcfd5e8576.png
[SouthEast 8]: /images/20211122/2663cd87a46741bfa066b7b0330b81ef.png
[SouthEast 9]: /images/20211122/2260d86c029d48469be12240859ff4b4.png
[SouthEast 10]: /images/20211122/5eb4806c267f44b8a751930676117fb9.png
[SouthEast 11]: /images/20211122/ee6f81b8c4ad4cbfb57075f50e5896db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h6ZW5nd2VpMTMxMw_size_16_color_FFFFFF_t_70]: /images/20211122/ba136b0ef6414301819fb7b33c1487d5.png