邻接矩阵无向图
程序员文章站
2023-12-23 19:22:58
...
邻接矩阵
无向图和有向图在邻接矩阵中的表示方法：
无向图和有向图大同小异，在这里只以无向图为例，代码部分通过简单调整即可对应编译有向图
邻接矩阵数据类型定义
#define MaxVertices 100 //定义最大容量
typedef struct{ //包含权的邻接矩阵的的定义
int Vertices[MaxVertices]; //顶点信息的数组
int Edge[MaxVertices][MaxVertices]; //边信息的数组
int numV; //顶点数
int numE; //边数
}AdjMatrix;- 1
- 2
- 3
- 4
- 5
- 6
- 7
以如关系图为例
根据上图，我们可以写出对应的邻接矩阵：
通过这个图可以看出，无向图对角线划分出来的两部分是互相对称的，由此即可通过创建无向图的邻接矩阵：
void CreateGraph(AdjMatrix *G) //图的生成函数
{
int n,e,vi,vj,w,i,j;
printf("请输入图的顶点数和边数（以空格分隔）：");
scanf("%d%d",&n,&e);
G->numV=n;G->numE=e;
for(i=0;i<n;i++) //图的初始化
for(j=0;j<n;j++)
{
if(i==j)
G->Edge[i][j]=0;
else
G->Edge[i][j]=32767;
}
for(i=0;i<n;i++)
for(i=0;i<G->numV;i++) //将顶点存入数组中
{
printf("请输入第%d个顶点的信息:",i+1);
scanf("%d",&G->Vertices[i]);
}
printf("\n");
for(i=0;i<G->numE;i++)
{
printf("请输入边的信息i,j,w(以空格分隔):");
scanf("%d%d%d",&vi,&vj,&w);
//若为不带权值的图，则w输入1
//若为带权值的图，则w输入对应权值
G->Edge[vi-1][vj-1]=w;//①
G->Edge[vj-1][vi-1]=w;//②
//无向图具有对称性的规律，通过①②实现
//有向图不具备此性质，所以只需要①
}
}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
创建完无向图对应的邻接矩阵，我们需要对输出的格式进行一下控制，使其尽量按照普通手写的方式输出
void DispGraph(AdjMatrix G) //输出邻接矩阵的信息
{
int i,j;
printf("\n输出顶点的信息（整型）:\n");
for(i=0;i<G.numV;i++)
printf("%8d",G.Vertices[i]);
printf("\n输出邻接矩阵:\n");
printf("\t");
for(i=0;i<G.numV;i++)
printf("%8d",G.Vertices[i]);
for(i=0;i<G.numV;i++)
{
printf("\n%8d",i+1);
for(j=0;j<G.numV;j++)
{
if(G.Edge[i][j]==32767) //两点之间无连接时权值为默认的32767，但输出时为了方便输出 "∞"
printf("%8s", "∞");
else
printf("%8d",G.Edge[i][j]);
}
printf("\n");
}
}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
完整程序如下：
#include<stdio.h>
#include<stdlib.h>
#define MaxVertices 100 //假设包含100个顶点
#define MaxWeight 32767 //不邻接时为32767，但输出时用 "∞"
typedef struct{ //包含权的邻接矩阵的的定义
int Vertices[MaxVertices]; //顶点信息的数组
int Edge[MaxVertices][MaxVertices]; //边的权信息的数组
int numV; //当前的顶点数
int numE; //当前的边数
}AdjMatrix;
void CreateGraph(AdjMatrix *G) //图的生成函数
{
int n,e,vi,vj,w,i,j;
printf("请输入图的顶点数和边数（以空格分隔）：");
scanf("%d%d",&n,&e);
G->numV=n;G->numE=e;
for(i=0;i<n;i++) //图的初始化
for(j=0;j<n;j++)
{
if(i==j)
G->Edge[i][j]=0;
else
G->Edge[i][j]=32767;
}
for(i=0;i<n;i++)
for(i=0;i<G->numV;i++) //将顶点存入数组中
{
printf("请输入第%d个顶点的信息(整型):",i+1);
scanf("%d",&G->Vertices[i]);
}
printf("\n");
for(i=0;i<G->numE;i++)
{
printf("请输入边的信息i,j,w(以空格分隔):");
scanf("%d%d%d",&vi,&vj,&w);
//若为不带权值的图，则w输入1
//若为带权值的图，则w输入对应权值
G->Edge[vi-1][vj-1]=w;//①
G->Edge[vj-1][vi-1]=w;//②
//无向图具有对称性的规律，通过①②实现
//有向图不具备此性质，所以只需要①
}
}
void DispGraph(AdjMatrix G) //输出邻接矩阵的信息
{
int i,j;
printf("\n输出顶点的信息（整型）:\n");
for(i=0;i<G.numV;i++)
printf("%8d",G.Vertices[i]);
printf("\n输出邻接矩阵:\n");
printf("\t");
for(i=0;i<G.numV;i++)
printf("%8d",G.Vertices[i]);
for(i=0;i<G.numV;i++)
{
printf("\n%8d",i+1);
for(j=0;j<G.numV;j++)
{
if(G.Edge[i][j]==32767)
//两点之间无连接时权值为默认的32767，
在无向图中一般用"0"表示，在有向图中一般用"∞",
这里为了方便统一输出 "∞"
printf("%8s", "∞");
else
printf("%8d",G.Edge[i][j]);
}
printf("\n");
}
}
int main()
{
AdjMatrix G;
CreateGraph(&G);
DispGraph(G);
}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
运行结果如下：
http://blog.csdn.net/qq_39630587/article/details/77374857