1.描述
设计算法求解以邻接表存储的有向图G中所有从src到dst长度为d的路径。
2.分析
通过DFS+清除访问标记visited的方法能求出所有从src到dst的所有路径(src到每个顶点的所有路径)。增加了新的限定,规定路径的长度为d(过滤出来)。
3.算法思想
- 使用DFS搜索src到dst长度为d的路径,将长度为d的路径保存到数组中并进行输出。
DFS每次往下走一个递归,实际上就是增加了一条,路径长度增加1.如果规定了要搜的路径长度,实际上能走的条数减少了1.通过这种方式过滤掉无关的路径。
4.手算示例
从4号顶点(src)到6号顶点(dst),长度为d的路径

在手算的时候心中一定要有递归执行过程的概念
递归 | 1 | 2 | 3 | 4 | 5 |
查找1 | DFS(4) | DFS(7) | DFS(6) | ||
查找2 | DFS(5) | DFS(6) | |||
查找3 | DFS(6) | ||||
查找4 | DFS(5) | DFS(6) | |||
查找5 | DFS(1) | DFS(3) | DFS(2) | DFS(6) | |
查找6 | DFS(2) | DFS(6) |
查找2搜到的路径已经超出了长度的限制,是不符合题目的要求,当路径中的结点数(DFS递归的层数超出d)大于d,继续从当前访问到的结点进行DFS就没有任何意义了,无需往下搜索。
通过手算发现,每次DFS往下走一次,路径中的顶点数量就增加一次,能搜的次数减少一次了。从而,每次往下走进行dfs的时候,次数就要减少一。如果次数减少到零,就无需再DFS。当DFS到的顶点v等于dst且能往下走的次数为0,说明找到了符合要求的路径。
5.代码
路径打印函数
void printPath(VertexType path[], int pathLength) { printf("Path: "); for (int i = 0; i < pathLength; i++) { printf("-> %d ", path[i]); } printf("\n"); }
全局变量
// 访问标记数组 bool visited[MAX_VERTEX] = { false }; VertexType path[MAX_VERTEX] = { 0 }; // 保存路径中的顶点数组 int pathLength = 0;
核心代码
注意限制条件,第16行和22行
/** * 使用DFS求src到dst长度为d的路径 * * @param alG - 邻接表存储的图 * @param src - 起始顶点 * @param dst - 目的顶点 * @param d - 路径长度 * * @return @c void */ void getPathLength(ALGraph alG, VertexType src, VertexType dst, int d) { visited[src] = true; // src顶点处于递归状态 path[pathLength++] = src; // 找到了符合要求的路径 if (src == dst && pathLength == d) { // 打印路径 printPath(path, pathLength); } // 不符合要求从邻居结点出发搜长度为d的路径 else if (src != dst && pathLength < d) { ArcNode* pNextArcNode = alG.vertices[src].first; int neighborVertex = 0; // 不断获取邻居顶点,从邻居结点开始找dst路径 while (pNextArcNode != NULL) { // 获取顶点编号 neighborVertex = pNextArcNode->adjvex; // neighborVertex顶点未在标记数组 if (!visited[neighborVertex]) { getPathLength(alG, neighborVertex, dst, d); } pNextArcNode = pNextArcNode->next; } } // 清除标记:删除路径中的最后一个顶点 visited[src] = false; pathLength--; }
6.运行
注意:图的类型为有向不带权图
数据准备
顶点数据:
vSet.txt
1 2 3 4 5 6 7
弧数据:
arcSet.txt
1 2 1 3 2 6 3 2 4 1 4 5 4 6 4 7 5 6 7 5 7 6
读取顶点信息
读取弧信息
创建图
调用DFS求d为3的路径
getPathLength(alG, 4, 6, 3);
运行结果
