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

本文主要是介绍【408DS算法题】039进阶-判断图中路径是否存在，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

对于给定的图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两种方式实现的图的路径的存在性判断。

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

这篇关于【408DS算法题】039进阶-判断图中路径是否存在的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---