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

弧数据：arcSet.txt

调用DFS求路径

getPath(alG, 4, 6);

运行结果