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

弧数据：arcSet.txt

读取顶点信息

读取弧信息

创建图

调用DFS求d为3的路径

getPathLength(alG, 4, 6, 3);

运行结果