图遍历：DFS深度搜索优先搜索及C语言代码实现

terry 2年前 (2023-09-27) 阅读数 70 #数据结构与算法

1.图遍历

在了解DFS算法之前，我们首先要了解什么是遍历。遍历的概念是：从某一点Start（通常是start或end）开始，依次访问数据结构中的每个数据，并且只访问一次。

2。 DFS简介

DFS（深度优先搜索）算法的特殊方法是：比某个点更深，当不能再往下走时，返回Go Forward，直到找到解或遍历所有的点。

在执行这种顺序访问序列时，存储操作动作的思想与数据结构（栈）非常相似。同时，由于堆栈的性质，我们可以通过递归来简化堆栈的创建，从而使用堆栈或递归来实现两类算法DFS方法。

算法步骤（递归或一致实现）

a) 访问指定的起始位置。

b) 如果除了当前访问点之外还有未访问过的点，则选择任意一个进行访问。如果没有，则返回到最后访问的点，直到穿过与起点相连的所有点。

c) 如果路线上还有未到过的点，请选择另一个点作为起点，然后重复前面的步骤。

3。 DFS图

我们直接用例子来解释一下。对于该图，访问顺序可以是（不唯一）：1-2-4-5-3

首先从1开始，在节点1中可以访问两个节点2和3，然后在按照顺序访问节点2按照我们定制的优先顺序。此时节点2被两个节点4和5访问，仍然是按顺序访问的。 4个节点，4个节点可以访问5个节点，5个节点不能继续下游访问，所以访问结束，4个节点回去。 4个节点不能有其他分支并且已经被访问过，所以返回到2个节点。，节点 2 的分支 4 和分支 5 都被访问过，所以我们返回到节点 1。目前只有节点 3 没有被访问过。访问节点3后，我们最终得到顺序：1-2-4-5-3

4。相关代码

对应的DFS算法模板如下：

void dfs()//参数用于表示状态 { 如果（达到最终状态） { //根据需要添加 return; } 如果（出界或非法）； if（特殊状态）//修剪，去掉一些不需要访问的场景，不一定是我家

返回 ；   for（扩展方法）  {  if（达到状态扩展方法是合法的）                     更改操作;//根据问号含义添加                       ;更新标签）；  //如果要恢复标记，要看题意  //如果是加（减号），就是回溯法  }    } }

对于图论（代码部分）选择，仅供参考，最重要的是记住上面的模板代码）：

//从pos开始，遍历无向图到深度//pos代表当前节点，G代表图，visited[]数组用于表示 Or 访问节点 void DFS(int pos,pGraph G, int 访问过[30 ]) { 节点 p; printf("%d",pos); //打印访问过的路径深度点 访问过 [POS] = 1; // 标记为已访问 p = g-> 顶点 [POS] .firstarc; / 判断是否遍历过相邻点 if (visited[p->adjvex]==0){ DFS(p->adjvex,G,vis已编辑）） ; p=p ->next;//向后移动一段，为以后的相邻点做准备 }}

在最早的搜索算法中的实际应用。例如，HTML搜索基于并使用DFS。时至今日，很多DFS算法仍然应用于精准小数据的定位操作，比如一些拓扑图、网络等。同时，DFS算法也是算法竞赛入门级的标准算法。公司入学考试的算法等

版权声明

本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。

上一篇：图像存储：系统设计、星码前向链C语言实例下一篇：图关系-邻接关系列表的概念和特点，C/C++语言代码实现

图遍历：DFS深度搜索优先搜索及C语言代码实现

版权声明

作者文章