1.描述
以邻接表存储的有向图中从src到dst是否存在路径。
2.算法思想
- 从src开始对图进行dfs,如果在dfs的过程中访问到了dst顶点,图中一定存在src到dst的路径。
- 否则,不存在src到dst的路径。
DFS的本质就是搜索一个结点src到另外顶点的一条路径。可以通过visit标记数组、源点src、终点dst、邻居结点访问方式,这四项控制好,怎么去根据题目设计好这四项,就能使用DFS求出任意题目要求的路径。
规则:在递归过程中,没有退出递归的顶点构成一条路径。DFS回退出去,再重新递归DFS到一个新的结点,代表又搜到了一条新的路径。
3.手算示例
从4号顶点(src)到6号顶点(dst),是否存在路径

在手算的时候心中一定要有递归执行过程的概念
递归 | 1 | 2 | 3 | 4 | 5 |
查找1 | DFS(4) | DFS(7) | DFS(6) | ||
查找2 | DFS(6) | ||||
查找3 | DFS(5) | ||||
查找4 | DFS(1) | DFS(2) | DFS(6) |
4.代码
// 访问标记数组 bool visited[MAX_VERTEX] = { false }; // 求某个顶点src到dst的路径 bool isExistPath(ALGraph alG, VertexType src, VertexType dst) { // 标记顶点已访问 visited[src] = true; // 找到路径 if (src == dst) return true; // 没找到路径,从邻居顶点查找是否存在 // src -> 邻居 -> 邻居 -> ...... -> dst ArcNode* pNextArcNode = alG.vertices[src].first; int neighborVertex = 0; bool ret = false; while (pNextArcNode != NULL) { neighborVertex = pNextArcNode->adjvex; if (!visited[neighborVertex]) ret = isExistPath(alG, neighborVertex, dst); if (ret) // 路径存在,返回 return true; pNextArcNode = pNextArcNode->next; } return false; }
5.运行
注意:图的类型为有向不带权图
数据准备
顶点数据:
vSet.txt
1 2 3 4 5 6 7
弧数据:
arcSet.txt
1 2 2 6 3 1 3 2 4 1 4 5 4 6 4 7 7 6
读取顶点信息
读取弧信息
创建图
调用DFS判路径
printf("isExit: %d\n", isExistPath(alG, 4, 6));
运行结果
