#include <stdio.h>
#include <malloc.h>
int n,m,sum,book[101],map[101][101];
//n是图的顶点数，m是图的边数
void initialise() //初始化图的矩阵
{
int i=0,j=0,a=0,b=0;
printf("请输入图中顶点数与路径数：\n");
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
map[i][j]=0;
else
map[i][j]=666666; //创建图的矩阵
printf("请输入图中存在路径的两点:\n");
for(i=1;i<=m;i++)
{
scanf("%d %d",&a,&b);
map[a][b]=1;
map[b][a]=1; //读入边初始化图的矩阵
}
return ;
}
void destroy() //销毁图，释放空间
{
/*int *p=&map[0][0];
for(int i=0;i<101;i++)
free(p+i);
int *q=&book[0];
for(int i=0;i<101;i++)
free(q+i);*/
for(int i=1;i<n;i++)
for(int j=1;j<n;j++)
map[i][j]=0;
for(int i=0;i<n;i++)
book[n]=0;
printf("图已成功销毁\n");
return ;
}
void dfs(int start) //深度优先遍历
{
book[start]=1;
printf("%d ",start);
sum++; //走过的顶点数加一
if(sum==n) //遍历完结束函数
return ;
for(int i=1;i<=n;i++)
{
if(map[start][i]==1&&book[i]==0) //有路且未走过
{
book[i]=1;
dfs(i); //递归
}
}
return ;
}
void pfs(int start)
{
int que[10001]={0},head=1,tail=1;
//队列初始化
que[tail]=start;
tail++;
book[start]=1;
while(head<tail)
{
start=que[head];
for(int i=1;i<=n;i++)
{
if(map[start][i]==1&&book[i]==0)
{
que[tail]=i;
tail++;
book[i]=1;
}
if(tail>n)
break;
}
head++;
}
printf("广度遍历结果如下:\n");
for(int i=1;i<tail;i++)
printf("%d ",que[i]);
printf("\n");
if(tail-1<n)
{
printf("非连通顶点为:");
for(int i=1;i<=n;i++)
{
if(book[i]==0)
printf("%d ",i);
}
printf("\n");
}
}
void connectedness() //判断是否为连通图
{
int que[10001]={0},head=1,tail=1,start=0;
//队列初始化
que[tail]=1;
tail++;
book[1]=1;
while(head<tail)
{
start=que[head];
for(int i=1;i<=n;i++)
{
if(map[start][i]==1&&book[i]==0)
{
que[tail]=i;
tail++;
book[i]=1;
}
if(tail>n)
break;
}
head++;
}
if(tail-1<n)
printf("该图为非连通图\n");
else
printf("该图为连通图\n");
}
int main()
{
initialise();
printf("深度遍历结果如下:\n");
//book[1]=1;
dfs(1); //深度优先遍历
printf("\n");
if(sum<n)
{
printf("非连通顶点为:");
for(int i=1;i<=n;i++)
{
if(book[i]==0)
printf("%d ",i);
}
printf("\n");
}
sum=0;
for(int i=0;i<=n;i++)
book[i]=0; //所有点恢复没有访问的状态
pfs(1); //广度优先遍历
for(int i=0;i<=n;i++)
book[i]=0;
connectedness(); //判断是否为连通图
destroy(); //销毁矩阵图
return 0;
}
