带权无向图的邻接矩阵表示法(C语言实现)

一、邻接矩阵表示法

​ 定义：所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。

​ 对于带权图而言，若顶点V_i 和 V_j 之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点V_i 和 V_j 不相连，则用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;
} 

九、测试

输入示例：

输入时只需要输入上三角部分或下三角部分(不含主对角线上的)即可。