第四次实验用邻接矩阵存储图
#include<stdio.h>
#include<stdlib.h>
#define Vertnum 9
typedef int Vertype; //顶点类型
typedef int Arctype;
typedef struct{
Vertype vexs[Vertnum]; //定义图的定点
数组
Arctype arcs[Vertnum][Vertnum]; //邻接
矩阵
}Mgraph; //定义图
Mgraph mgraph; //定义一个图类型的全局变
量
int visited[Vertnum]; //访问标记数组,用于
标记节点是否已访问
void Creat_graph(int vertex1,int vertex2) //建
立图的函数
{ mgraph.arcs[vertex1][vertex2]=1;
mgraph.arcs[vertex2][vertex2]=1;
}
void print_Mgraph() //输出邻接矩阵的数据
{ int i,j;
for(i=1;i<Vertnum;i++)
{ for(j=1;j<Vertnum;j++)
printf("%2d",mgraph.arcs[i][j]);
printf("");
}
}
void DFSm(int vertx) //深度优先算法遍历图
的函数(只能遍历连通图)
{ int i;
visited[vertx]=1; //将被访问的节点进行
标记
printf("[%d]=>",vertx); //访问该节点信息
for(i=1;i<Vertnum;i++)
if((visited[i]!=1)&&(mgraph.arcs[vertx][i]))
DFSm(i); //用深度优先算法访问,
未被访问的邻接节点
}
void main()
{ int i,j;
int node[20][2]={{1,2},{2,1},{1,3},{3,1},
{2,4},{4,2},{2,5},{5,2},{3,6},{6,3},{3,7},
{7,3},{4,8},{8,4},{5,8},{8,5},{6,8},{8,6},{7,8},
{8,7}};
for(i=0;i<Vertnum;i++)
visited[i]=0; //将标记数组初始化
for(i=0;i<Vertnum;i++)
mgraph.vexs[i]=i; //给图的顶点赋值
for(i=0;i<Vertnum;i++)
{ for(j=0;j<Vertnum;j++)
{ mgraph.arcs[i][j]=0; //将邻接矩阵
初始化为零
}
}
for(i=0;i<20;i++)
Creat_graph(node[i][0],node[i][1]); //建
立图
printf(" 输出邻接矩阵");
print_Mgraph(); //输出邻接矩阵
printf(" 深 度 优 先 算 法 遍 历 图 的 结 果
为:");
printf("[开始]=>");
for(i=1;i<Vertnum;i++)
if(!visited[i]) //将 DFSm 只能遍历连通
图的缺点进行优化
DFSm(1);
printf("[结束]");
}
实验结果截图如下:
评论0