108 lines
2.0 KiB
C++
108 lines
2.0 KiB
C++
//#include<string>
|
||
|
||
#include <iostream>
|
||
|
||
#include "MGraph.h"
|
||
#include "LinkQueue.h"
|
||
using namespace std;
|
||
|
||
void DispMenu()
|
||
{
|
||
cout<<"\n请选择你要的操作"<<endl;
|
||
cout<<" 1. 建立图"<<endl;
|
||
cout<<" 2. 判断两顶点的连通性"<<endl;
|
||
cout<<" 3. 判断图的连通性"<<endl;
|
||
cout<<" 4. 显示图"<<endl;
|
||
cout<<" 0. 退出"<<endl;
|
||
}
|
||
|
||
|
||
|
||
//算法6.14 判断两顶点是否连通
|
||
template<class DT>
|
||
bool IsConected(MGraph<DT> G, int i, int j)
|
||
{
|
||
int k;
|
||
for(k=0;k<G.vexnum;k++)
|
||
visited[i]=false;
|
||
BFS(G,i);
|
||
if(visited[j]==false)
|
||
return false;
|
||
else
|
||
return true;
|
||
}
|
||
|
||
|
||
|
||
// 算法6.15 判断图的连通性
|
||
template<class DT>
|
||
bool IsGraphConected(MGraph<DT> G)
|
||
{
|
||
int i,flag=1;
|
||
for(i=0;i<G.vexnum;i++) // 访问标志初始化
|
||
visited[i]=0;
|
||
DFS2(G,0); // 遍历图
|
||
for(i=0;i<G.vexnum;i++)
|
||
if(visited[i]==0) // 如果未遍历到所有顶点
|
||
{
|
||
flag=0;break; // 图不连通
|
||
}
|
||
return flag; // 否则，图连通
|
||
}
|
||
|
||
bool visited[MAX_VEXNUM]={false};
|
||
|
||
void main()
|
||
{
|
||
char u,v;
|
||
int i,j,k;
|
||
MGraph<char> G;
|
||
int choice;
|
||
do
|
||
{
|
||
DispMenu();
|
||
cin>>choice;
|
||
switch(choice)
|
||
{
|
||
case 1: // 创建无向图
|
||
CreateUDG(G);
|
||
cout<<endl;
|
||
cout<<"创建的图为："<<endl;
|
||
DispG(G);
|
||
break;
|
||
case 2: // 判断两顶点的连通性
|
||
cout<<"请输入两顶点值: ";
|
||
cin>>u>>v;
|
||
i=LocateVex(G,u);
|
||
j=LocateVex(G,v);
|
||
if(i==-1 ||j==-1 || i==j) // 顶点不存在
|
||
cout<<"\n顶点不存在或两顶点相同 "<<endl;
|
||
else
|
||
{
|
||
if(IsConected(G,i,j))
|
||
cout<<"\n"<<u<<"和"<<v<<"之间连通!"<<endl;
|
||
else
|
||
cout<<"\n"<<u<<"和"<<v<<"之间不连通!"<<endl;
|
||
}
|
||
cout<<endl;
|
||
break;
|
||
case 3: // 判断图的连通性
|
||
if(IsGraphConected(G))
|
||
cout<<"\n此图连通！ "<<v<<endl;
|
||
else
|
||
cout<<"\n此图不连通！"<<endl;
|
||
cout<<endl;
|
||
break;
|
||
case 4: // 显示图
|
||
DispG(G);
|
||
cout<<endl;
|
||
break;
|
||
case 0:
|
||
cout<<"\n结束运行，Bye-Bye!"<<endl;
|
||
break;
|
||
default:
|
||
cout<<"\n选择不合理，请重选!"<<endl;
|
||
}
|
||
}while(choice!=0);
|
||
}
|