带权无向图的邻接矩阵表示法(C语言实现)
一、邻接矩阵表示法
定义：所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。
对于带权图而言，若顶点Vi 和 Vj 之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点Vi 和 Vj 不相连，则用0或∞来代表这两个顶点之间不存在边。
例如，对于下面这样一个图：
我们可以得到其邻接矩阵：
注：括号内的0、1、2、3代表其二维数组的下标。
容易发现，带权邻接矩阵有以下特点：①关于主对角线元素对称；②非0的对应位置上的值即为边的权值。
如果是不带权，那么有边的对应位置为1，没边的位置为0，同样也是关于主对角线元素对称。
二、本次程序实现的功能
-
创建无向图的邻接矩阵
-
输出无向图对应的邻接矩阵
-
输出顶点集合
-
判断两顶点是否邻接，即是否存在直接相连的边
三、带权无向图的结构体定义
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct {
VertexType Vex[MaxVertexNum]; //顶点表 MaxVertexNum是最大的顶点数目,下同
EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
int vexnum, arcnum; //图的当前顶点数和边数
}MGraph;//基于邻接矩阵法的带权无向图
四、创建无向图及邻接矩阵
由于比较简单，就不多解释了。值得注意的是，要好好利用无向图的邻接矩阵关于主对角线对称的特性，所以输入边权值时只需要输入上三角或下三角。
void CreateMGraph(MGraph *G)
{
int i,j,k,w;
//先确定顶点数和边数
printf("请输入顶点数和边数,用空格隔开:\n");
scanf("%d %d",&G->vexnum,&G->arcnum);
fflush(stdin);//清空输入缓冲区,否则可能无法正常读取输入
//依次输入顶点的值
printf("请依次输入顶点的值:\n");
for(int i = 0;i < G->vexnum; i++)
{
printf("输入第%d个顶点信息:\n",i+1);
scanf("%c",&G->Vex[i]); //接收值放入顶点表中
fflush(stdin);//清空输入缓冲区,否则可能无法正常读取输入
}
//初始化邻接矩阵
for(i = 0;i < G->vexnum; i++)
for(j = 0;j <G->vexnum; j++)
G->Edge[i][j] = 0;//开始时全部初始化为0,也可以用∞
//建立邻接矩阵
for (k = 0; k < G->arcnum; k++)
{
printf("输入边<vi,vj>的下标i,下标j和权w:\n");
scanf("%d%d%d", &i, &j, &w); //输入边<vi,vj>上的权值w
G->Edge[i][j] = w;
G->Edge[j][i] = G->Edge[i][j]; //无向图矩阵是对称的
}
}
五、输出邻接矩阵
本质就是遍历一个二维数组。
//输出邻接矩阵
void PrintMatrix(MGraph G)
{
int i,j;
printf("邻接矩阵表示如下:\n");
for (i = 0; i < G.vexnum; i++)
{
for (j = 0; j < G.vexnum; j++)
printf("%-10d", G.Edge[i][j]);//左对齐输出
printf("\n");
}
}
六、输出顶点集合
本质是遍历一维数组。
//输出顶点集合
void PrintVex(MGraph G)
{
printf("\n顶点集合为：");
for(int i=0;i<G.vexnum;i++)
printf("%c ",G.Vex[i]);
printf("\n");
}
七、判断两顶点是否邻接
接收的参数是两个顶点的值，因此需要在顶点表中找到其下标，然后判断其对应位置的邻接矩阵的值是否大于0，如果是大于0即说明邻接，否则不邻接。
注：如果找顶点的下标操作比较频繁，可以考虑再封装成一个函数。
//判断两个顶点之间是否邻接
bool Is_Edge_Exist(MGraph G, VertexType d1, VertexType d2)
{
int i,j,k;
for(k=0;k<G.vexnum;k++)
{
if(G.Vex[k]==d1)
i = k;//找到顶点对应的下标
if(G.Vex[k]==d2)
j = k;//找到顶点对应的下标
}
return G.Edge[i][j]>0?1:0;
}
八、全部代码
#include<stdio.h>
#define MaxVertexNum 10 //顶点数目的最大值
#include<stdbool.h> //根据C99标准,C语言使用bool类型需要添加这个头文件
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct {
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
int vexnum, arcnum; //图的当前顶点数和边数
}MGraph;//基于邻接矩阵法的带权无向图
void CreateMGraph(MGraph *G)
{
int i,j,k,w;
//先确定顶点数和边数
printf("请输入顶点数和边数,用空格隔开:\n");
scanf("%d %d",&G->vexnum,&G->arcnum);
fflush(stdin);//清空输入缓冲区,否则可能无法正常读取输入
//依次输入顶点的值
printf("请依次输入顶点的值:\n");
for(int i = 0;i < G->vexnum; i++)
{
printf("输入第%d个顶点信息:\n",i+1);
scanf("%c",&G->Vex[i]); //接收值放入顶点表中
fflush(stdin);//清空输入缓冲区,否则可能无法正常读取输入
}
//初始化邻接矩阵
for(i = 0;i < G->vexnum; i++)
for(j = 0;j <G->vexnum; j++)
G->Edge[i][j] = 0;//开始时全部初始化为0,也可以用∞
//建立邻接矩阵
for (k = 0; k < G->arcnum; k++)
{
printf("输入边<vi,vj>的下标i,下标j和权w:\n");
scanf("%d%d%d", &i, &j, &w); //输入边<vi,vj>上的权值w
G->Edge[i][j] = w;
G->Edge[j][i] = G->Edge[i][j]; //无向图矩阵是对称的
}
}
//输出邻接矩阵
void PrintMatrix(MGraph G)
{
int i,j;
printf("邻接矩阵表示如下:\n");
for (i = 0; i < G.vexnum; i++)
{
for (j = 0; j < G.vexnum; j++)
printf("%-10d", G.Edge[i][j]);//左对齐输出
printf("\n");
}
}
//输出顶点集合
void PrintVex(MGraph G)
{
printf("\n顶点集合为：");
for(int i=0;i<G.vexnum;i++)
printf("%c ",G.Vex[i]);
printf("\n");
}
//判断两个顶点之间是否邻接
bool Is_Edge_Exist(MGraph G, VertexType d1, VertexType d2)
{
int i,j,k;
for(k=0;k<G.vexnum;k++)
{
if(G.Vex[k]==d1)
i = k;//找到顶点对应的下标
if(G.Vex[k]==d2)
j = k;//找到顶点对应的下标
}
return G.Edge[i][j]>0?1:0;
}
int main()
{
MGraph G;//无向图
CreateMGraph(&G);//创建图
PrintMatrix(G);//输出邻接矩阵
PrintVex(G);//输出顶点
//判断两个顶点是否邻接
VertexType d1,d2;
d1 = 'A';
d2 = 'B';
if(Is_Edge_Exist(G,d1,d2))
printf("\n%c和%c邻接!\n",d1,d2);
else
printf("\n%c和%c不邻接!\n",d1,d2);
d2 = 'C';
if(Is_Edge_Exist(G,d1,d2))
printf("\n%c和%c邻接!\n",d1,d2);
else
printf("\n%c和%c不邻接!\n",d1,d2);
return 0;
}
九、测试
输入示例：
输入时只需要输入上三角部分或下三角部分(不含主对角线上的)即可。文章来源：https://www.toymoban.com/news/detail-571820.html
文章来源地址https://www.toymoban.com/news/detail-571820.html
到了这里，关于带权无向图的邻接矩阵表示法(C语言实现)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![数据结构05：树的定义与双亲、孩子表示法[更新中]](https://imgs.yssmx.com/Uploads/2024/02/476408-1.png)
