37.2° Blog

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));

运行结果