深度优先搜索（DFS）算法详解 |
您所在的位置：网站首页 › 算法dfs是什么意思 › 深度优先搜索（DFS）算法详解 |
|
深度优先搜索（Depth First Search）简称深搜或者 DFS，是遍历图存储结构的一种算法，既适用于无向图（网），也适用于有向图（网）。
所谓图的遍历，简单理解就是逐个访问图中的顶点，确保每个顶点都只访问一次。 首先通过一个样例，给大家讲解深度优先搜索算法是如何实现图的遍历的。 图 1 深度优先搜索算法遍历无向图 深度优先搜索算法遍历图 1 无向图的整个过程是： 1) 初始状态下，无向图中的所有顶点都是没有被访问过的，因此可以任选一个顶点出发，遍历整个无向图。 假设从 V1 顶点开始，先访问 V1 顶点，如下图所示： 图 2 访问顶点 1 2) 紧邻 V1 的顶点有两个，分别是 V2 和 V3，它们都没有被访问过，从它们中任选一个，比如访问 V2，如下图所示： 图 3 访问顶点 V2 3) 紧邻 V2 的顶点有三个，分别是 V1、V4 和 V5，尚未被访问的有 V4 和 V5，从它们中任选一个，比如访问 V4，如下图所示： 图 4 访问顶点 V4 4) 紧邻 V4 的顶点有两个，分别是 V2 和 V8，只有 V8 尚未被访问，因此访问 V8，如下图所示： 图 5 访问顶点 V8 5) 紧邻 V8 的顶点有两个，分别是 V4 和 V5，只有 V5 尚未被访问，因此访问 V5，如下图所示： 图 6 访问顶点 V5 6) 和 V5 相邻的顶点有两个，分别是 V2 和 V8，它们都已经访问过了。也就是说，此时从 V5 出发，找不到任何未被访问的顶点了。 这种情况下，深度优先搜索算法会回退到之前的顶点，查看先前有没有漏掉的、尚未访问的顶点： 从 V5 回退到 V8，找不到尚未访问的顶点； 从 V8 回退到 V4，还是找不到尚未访问的顶点； 从 V4 回退到 V2，也还是找不到尚未访问的顶点； 从 V2 回退到 V1，发现 V3 还没有被访问。 于是，下一个要访问的顶点就是 V3，如下图所示： 图 7 访问顶点 V3 7) 紧邻 V3 的顶点有三个，分别是 V1、V6 和 V7，尚未访问的有 V6 和 V7，因此从它们中任选一个，比如访问 V6，如下图所示： 图 8 访问顶点 V6 8) 紧邻 V6 的顶点有两个，分别是 V3 和 V7，只有 V7 还没有访问，因此访问 V7，如下图所示： 图 9 访问顶点 V7 9) 紧邻 V7 顶点有 V6 和 V3，但它们都已经访问过了，此时面临的情况和第 6 步完全一样，深度优先搜索算法的解决方法也是一样的： 从 V7 回退到 V6，依然找不到尚未访问的顶点； 从 V6 回退到 V3，依然找不到尚未访问的顶点； 从 V3 回退到 V1，依然找不到尚未访问的顶点； V1 是遍历图的起始顶点，回退到 V1 还找不到尚未访问的顶点，意味着以 V1 顶点为突破口，能访问的顶点全部已经访问完了。这种情况下，深度优先搜索算法会从图的所有顶点中重新选择一个尚未访问的顶点，从该顶点出发查找尚未访问的其它顶点。 从图 9 可以看到，图中已经没有尚未访问的顶点了，此时深度优先搜索算法才执行结束。对于连通图来说，深度优先搜索算法从一个顶点出发就能访问图中所有的顶点。但是对于非连通图来说，深度优先搜索算法必须从各个连通分量中选择一个顶点出发，才能访问到所有的顶点。 深度优先搜索算法的具体实现 所谓深度优先搜索，就是从图中的某个顶点出发，不停的寻找相邻的、尚未访问的顶点： 如果找到多个，则任选一个顶点，然后继续从该顶点出发； 如果一个都没有找到，则回退到之前访问过的顶点，看看是否有漏掉的； 假设从顶点 V 出发，则最终还会回退到顶点 V。此时，深度优先搜索算法会从所有顶点中重新找一个尚未访问的顶点，如果能找到，则以同样的方式继续寻找其它未访问的顶点；如果找不到，则算法执行结束。 通常情况下，深度优先搜索算法访问图中顶点的顺序是不唯一的，即顶点的访问序列可能有多种（≥1）。 图的存储结构有很多种，大体上可以分为顺序存储和链式存储（又细分为邻接表结构、十字链表结构和邻接多重表结构），各个存储结构有自己的特点。选用不同的存储结构，深度优先搜索算法的具体实现不同，但算法的思想是不变的。 这里以图的顺序存储结构为例，深度优先搜索算法的 C 语言实现代码如下： #include #define MAX_VERtEX_NUM 20 //顶点的最大个数 #define VRType int //表示顶点之间关系的类型, 0 表示不相邻，1 表示相邻 #define VertexType int //图中顶点的数据类型 #define States int typedef enum { false, true }bool; //定义bool型常量 bool visited[MAX_VERtEX_NUM]; //设置全局数组，标记图中的各个顶点是否被访问过 typedef struct { VRType adj; //用 1 或 0 表示是否相邻； }ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM]; typedef struct { VertexType vexs[MAX_VERtEX_NUM]; //存储图中的顶点 AdjMatrix arcs; //二维数组，记录顶点之间的关系 int vexnum, arcnum; //记录图的顶点数和弧（边）数 }MGraph; //根据顶点数据，返回顶点在二维数组中的位置下标 int LocateVex(MGraph* G, VertexType v) { int i = 0; //遍历一维数组，找到变量v for (; i < G->vexnum; i++) { if (G->vexs[i] == v) { break; } } //如果找不到，输出提示语句，返回-1 if (i > G->vexnum) { printf("no such vertex.\n"); return -1; } return i; } //构造无向图 States CreateDN(MGraph* G) { int i, j, n, m; int v1, v2; scanf("%d,%d", &(G->vexnum), &(G->arcnum)); for (i = 0; i < G->vexnum; i++) { scanf("%d", &(G->vexs[i])); } for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { G->arcs[i][j].adj = 0; } } for (i = 0; i < G->arcnum; i++) { scanf("%d,%d", &v1, &v2); n = LocateVex(G, v1); m = LocateVex(G, v2); if (m == -1 || n == -1) { printf("no this vertex\n"); return -1; } G->arcs[n][m].adj = 1; G->arcs[m][n].adj = 1;//无向图的二阶矩阵沿主对角线对称 } return 1; } int FirstAdjVex(MGraph G, int v) { int i; //对于数组下标 v 处的顶点，找到第一个和它相邻的顶点，并返回该顶点的数组下标 for (i = 0; i < G.vexnum; i++) { if (G.arcs[v][i].adj) { return i; } } return -1; } int NextAdjVex(MGraph G, int v, int w) { int i; //对于数组下标 v 处的顶点，从 w 位置开始继续查找和它相邻的顶点，并返回该顶点的数组下标 for (i = w + 1; i < G.vexnum; i++) { if (G.arcs[v][i].adj) { return i; } } return -1; } void DFS(MGraph G, int v) { int w; printf("%d ", G.vexs[v]); //访问第 v 个顶点 visited[v] = true; //将第 v 个顶点的标记设置为true //对于与第 v 个顶点相邻的其它顶点，逐个调用深度优先搜索算法 for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) { //如果该顶点的标记为false，证明尚未被访问，就调用深度优先搜索算法 if (!visited[w]) { DFS(G, w); } } } //深度优先搜索 void DFSTraverse(MGraph G) { int v; //visit数组记录各个顶点是否已经访问过，全部初始化为 false for (v = 0; v < G.vexnum; ++v) { visited[v] = false; } //对于每个标记为false的顶点，都调用一次深度优先搜索算法 for (v = 0; v < G.vexnum; v++) { //如果该顶点的标记位为false，就调用深度优先搜索算法 if (!visited[v]) { DFS(G, v); } } } int main() { MGraph G; //建立一个图 CreateDN(&G); //初始化图 DFSTraverse(G);//深度优先搜索图 return 0; } 程序中，为了确保每个顶点只访问一次，借助了一个名为 visited 的一维数组，专门用来存储各个顶点的访问状态，用 0 表示未被访问，用 1 表示已经访问过。visited 数组中的访问状态和 vexs 数组中存储的顶点是一一对应的，比如 vexs[1] 顶点的访问状态就记录在 visited[1] 的位置。 用 1~8 分别表示图 1 中的顶点 V1~V8，程序的执行结果为：8,9 1 2 3 4 5 6 7 8 1,2 2,4 2,5 4,8 5,8 1,3 3,6 6,7 7,3 1 2 4 8 5 3 6 7 实现图的遍历，除了使用本节讲解的深度优先搜索算法外，还可以使用广度优先搜索算法。 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |