1.描述
设计算法求解以邻接表存储的有向图G中所有从src到dst的简单路径。
2.分析
如何把这个路径弄出来?
路径中的结点可以重复出现在别的路径中,如何解决访问过的结点出现在别的路径中这种情况。
3.算法思想
- 使用DFS搜索所有src到dst的简单路径,并用数组将路径中的顶点保存。
规律:顶点的递归一旦退出,那么就代表这条路径已经搜索完成了。依照这个手算发现的DFS规律,可以放心的清楚掉递归完成的顶点标记了,能确定同一条路径不会重复访问,然后图中所有以src开始的路径都能通过DFS搜索到。
至关重要:DFS中的visited标记是为了确保顶点在DFS序列中不会重复出现,但是这个跟不同路径中顶点重复出现不是一回事。
主要过程:在递归的访问到顶点的时候,直接将顶点保存到数组中。当顶点w退出递归的时候,就删除数组中的这个顶点,代表以递归访问到的顶点开头
V->...->r->wi
路径都访问完毕,那么下一次是从V->...->r->wj->....
开头的路径。所有开头的路径加一起就构成了图中所有的路径。蚂蚁搬家的方式去搜索路径。
4.手算示例
从4号顶点(src)到6号顶点(dst),是否存在路径

在手算的时候心中一定要有递归执行过程的概念
递归 | 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) |
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;
核心代码
/** * 使用DFS求src到dst的路径 * * @param alG - 邻接表存储的图 * @param src - 起始顶点 * @param dst - 目的顶点 * * @return @c void */ void getPath(ALGraph alG, VertexType src, VertexType dst) { visited[src] = true; // src顶点处于递归状态 path[pathLength++] = src; // 符合条件,输出路径 if (src == dst) { // 打印路径 printPath(path, pathLength); } // 若不符合,从邻居结点开始搜索 else { ArcNode* pNextArcNode = alG.vertices[src].first; int neighborVertex = 0; // 不断获取邻居顶点,从邻居结点开始找dst路径 while (pNextArcNode != NULL) { // 获取顶点编号 neighborVertex = pNextArcNode->adjvex; // neighborVertex顶点未在标记数组 if (!visited[neighborVertex]) { getPath(alG, neighborVertex, dst); } 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求路径
getPath(alG, 4, 6);
运行结果
