【408DS算法题】039进阶-判断图中路径是否存在

Index

• • 题目
  • 分析实现
  • 总结

题目

对于给定的图G，设计函数实现判断G中是否含有从start结点到stop结点的路径。

分析实现

对于图的路径的存在性判断，有两种做法：（本文的实现均基于邻接矩阵存储方式的图）

1.图的BFS

BFS的思路相对比较直观——从起始结点出发进行层次遍历，遍历过程中遇到结点i就表示存在路径start->i，故只需判断每个结点i是否就是stop。

具体实现如下：

// BFS版本判断路径存在
bool hasPathBFS(Graph& G, int start, int stop){
    if (start == stop)
        return true;
        
    vector<bool> visited(G.vexnum, false);
    queue<int> q;
    q.push(start);
    visited[start] = true;
    
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int i=0; i<G.vexnum; i++){
            // 没有边
            if(G.edge[cur][i] == 0){
                continue;
            }
            // 找到路径
            if(i == stop){
                return true;
            }
            if(!visited[G.edge[cur][i]]){
                q.push(i);
                visited[i] = true;
            }
        }
    }
    return false;
}

2.图的DFS

理解的图DFS版本的思想，首先需要根据递归的思想，推理出递归函数的作用——判断图中是否存在路径cur->stop，再将这一“功能”运用到遍历中，思路就会非常简单。

具体实现如下：

// DFS实现辅助函数
bool hasPathDFSUtil(Graph& G, int cur, int stop, vector<bool>& visited){
    if(cur == stop){
        return true;
    }
    visited[cur] = true;
    for(int i = 0; i < G.vexnum; i++){
        // 重点递归判断 - 存在边[cur-i] + 未访问过i + *存在路径[i-stop]
        if(G.edge[cur][i] == 1 && !visited[i] 
            && hasPathDFSUtil(G, i, stop, visited)){
            return true;
        }
    }
}
// DFS判断路径存在
bool hasPathDFS(Graph& G, int start, int stop){
    vector<bool> visited(G.vexnum, false);
    return hasPathDFSUtil(G, start, stop, visited);
}

总结

以上就是通过BFS和DFS两种方式实现的图的路径的存在性判断。

对于递归函数，刚开始尝试的时候总是会想不到思路。
对此，只需去想递归函数的统一的实现思路——假设函数功能已经实现，先写出递归基，再运用“更小规模”的函数调用来实现递归函数。