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

本文主要是介绍【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);
}