分享程序员开发的那些事...
更新时间：2022-08-22 08:31:59
4.2 给定有向图，设计一个算法，找出两个结点之间是否存在一条路径。
根据题意，给定一个有向图和起点终点，判断从起点开始，是否存在一条路径可以到达终点。 考查的就是图的遍历，从起点开始遍历该图，如果能访问到终点， 则说明起点与终点间存在路径。稍微修改一下遍历算法即可。
使用广度优先遍历实现代码：
#include<iostream> #include<queue> #include<cstring> using namespace std; const int n=4; bool visited[n]; queue<int> q; bool isroute(int matrix[][4],int src,int des) { int i; visited[src]=true; q.push(src); while(!q.empty()) { int tmp=q.front(); q.pop(); for(i=0;i<n;i++) { if(matrix[tmp][i]&&!visited[i]) { visited[i]=true; if(visited[des]) return true; q.push(i); } } } return false; } int main() { memset(visited,false,sizeof(visited)); int matrix[n][n]={{0,1,1,1},{1,0,1,0},{1,1,0,1},{1,0,1,0}}; cout<<isroute(matrix,1,3)<<endl; }
DFS
#include<iostream> #include<queue> #include<cstring> using namespace std; const int n=4; bool visited[n]; queue<int> q; //DFS bool isroute(int matrix[][4],int src,int des) { int i; visited[src]=true; for(i=0;i<n;i++) { if(matrix[src][i]&&!visited[i]) isroute(matrix,i,des); } return visited[des]; } int main() { memset(visited,false,sizeof(visited)); int matrix[n][n]={{0,0,0,1},{1,0,1,0},{1,1,0,0},{0,0,0,0}}; cout<<isroute(matrix,3,1)<<endl; }