首页 > 代码库 > careercup-树与图 4.2
careercup-树与图 4.2
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;//DFSbool 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;}
careercup-树与图 4.2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。