Question

如何判断有向图是否存在环路？图是用邻接矩阵来存储的

Answer 1

#include"utility.h"
#include"adj_matrix_undir_graph.h"
#include"adj_list_dir_graph.h"
#include"dfs.h"
#include"bfs.h"

int main(void)
{
int n,j=0,i=0;
int m,e,b=0;
char vexs[20],c;
char nums[20];

cout<<"输入无向图的顶点个数n:"<<endl;
cin>>n;
cout<<"输入顶点元素："<<endl;
for(i=0;i<n;i++)
{
cout<<"请输入第"<<j<<"个结点"<<endl;
cin>>vexs[i];
j++;
}

cout<<"输出无向图的邻接矩阵："<<endl;

AdjMatrixUndirGraph<char> aundir(vexs,n);
for(i=0;i<n;i++)
{
for(int v=1;v<n;v++)
{
cout<<"输入Y/N，是否插入边:";
cin>>c;
if(c == 'Y' )
aundir.InsertEdge(i,v);
}
}
Display(aundir);

cout<<"请输入有向图的顶点个数m：";
cin>>m;
for(int a=0;a<m;a++)
{
cout<<"输入第"<<b<<"个顶点数据";
cin>>nums[a];
b++;
}

AdjListDirGraph<char> dir(nums,m);

for(int k=0;k<m;k++)
{
for(e=0;e<m;e++)
{
cout<<"是否插入边V"<<k<<",V"<<e<<":";
cin>>c;
if(c == 'Y' )
dir.InsertEdge(k,e);
}
}
Display(dir);

cout<<"无向图的深度遍历：";
DFSTraverse<char>(aundir,Write<char>);
cout<<endl;
cout<<"无向图的广度遍历：";
BFSTraverse<char>(aundir,Write<char>);

cout<<endl;
cout<<"有向图的深度遍历：";
DFSTraverse<char>(dir,Write<char>);
cout<<endl;
cout<<"有向图的广度遍历：";
BFSTraverse<char>(dir,Write<char>);

Answer 2

bfs应该可以，不知道floyd是不是可以，好久没用了，应该可以