图的邻接矩阵数据结构代码实现

末蓝、 2023-10-17 16:21 117阅读 0赞

邻接 [矩阵][Link 1]（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V=\{v1,v2,…,vn\} \[1\]   。G的邻接矩阵是一个具有下列性质的n阶方阵：

①对 [无向图][Link 2]而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0， [有向图][Link 3]则不一定如此。

②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。

③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有[对称关系][Link 4]，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。

**\#include<stdio.h>**

**\#define infinity 1000**

**\#define MAX\_VERTEX\_NUM 100  
typedef enum\{DG,DN,UDG,UDN\} GraphKind;  
typedef struct \{  
int vexs\[MAX\_VERTEX\_NUM\];  
int arcs\[MAX\_VERTEX\_NUM\]\[MAX\_VERTEX\_NUM\];  
int vexnum,arcnum;  
GraphKind kind;  
\}MGraph;  
int LocateVex(MGraph G,int v)\{  
for(int i=0;i<G.vexnum;i++)\{  
if(G.vexs\[i\]==v)return i;  
\}  
\}  
void CreateUDN(MGraph &G)\{  
int i,j,k;  
G.kind=UDN;//图的类型为无向网  
printf("输入顶点个数和弧的个数：\\n");  
scanf("%d%d",&G.vexnum,&G.arcnum);//输入顶点个数，弧额条数，以及是否有关于弧的相关信息  
printf("输入各个顶点的名称（数字）：\\n");  
for(i=0;i<G.vexnum;i++)  
scanf("%d",&G.vexs\[i\]);//输入各个顶点，这里顶点的数据类型默认为int类型  
for(i=0;i<G.vexnum;i++)  
for(j=0;j<G.vexnum;j++)  
G.arcs\[i\]\[j\]=0;//初始化图  
printf("输入各条弧的两个顶点和权值：\\n");  
for(k=0;k<G.arcnum;k++)\{  
int v1,v2,weight;  
scanf("%d %d %d",&v1,&v2,&weight);//输入弧的两个顶点  
i=LocateVex(G,v1);j=LocateVex(G,v2);//寻找两个顶点在矩阵中的位置  
G.arcs\[i\]\[j\]=weight;  
G.arcs\[j\]\[i\]=G.arcs\[i\]\[j\];//置<v1,v2>的对称弧<v2,v1>  
\}  
\}  
void Print(MGraph G)\{  
for(int i=0;i<G.vexnum;i++)\{  
for(int j=0;j<G.vexnum;j++)  
printf("%d ",G.arcs\[i\]\[j\]);  
printf("\\n");  
\}  
\}  
int main()\{  
MGraph G;  
CreateUDN(G);  
Print(G);  
return 0;  
\}**

代码已实现！

[Link 1]: https://baike.baidu.com/item/%E7%9F%A9%E9%98%B5
[Link 2]: https://baike.baidu.com/item/%E6%97%A0%E5%90%91%E5%9B%BE
[Link 3]: https://baike.baidu.com/item/%E6%9C%89%E5%90%91%E5%9B%BE
[Link 4]: https://baike.baidu.com/item/%E5%AF%B9%E7%A7%B0%E5%85%B3%E7%B3%BB