题目描叙:
无向图的表示方法邻接矩阵,需打印到屏幕。有权。
分析:邻接矩阵的核心思想便是顶点表和边表。
我们可以定义一个结构体,里面包含一个顶点表(即一个vexs一维数组),一个边表(即一个arc二维数组),还有两个整形变量(即一个表示为顶点数,另外一个表示为边数)。我们将二维数组初始化为无穷大(在此程序中用65535表示无穷大)。如果顶点i到顶点j有边(即此两个顶点是连接的),那个arc[ i ][ j ]里面的值即顶点i与顶点j之间的权。因为,二维数组一开始初始化为无穷大。所以我们可以知道,如果二维数组里面的值不是无穷大的,则此值的下标i和下标j分别代表顶点i和顶点j。且i和j顶点是有边连接的。
因为是无向图,所以顶点i能到顶点j就表示了顶点j能到顶点i。且他们之间的权是相同的。最后打印出来会发现,二维数组是关于主对角线对称的。 我在这个程序中将下标i和下标j相同的位置的值置位0(即权为0)。
#include"stdio.h"
typedef char VertexType; //顶点类型
typedef int EdgeType; //边的类型
#define MAXVEX 100 //最大顶点数
#define INFINITY 65535 //表无穷。权的无穷大,即权不存在
typedef struct
{
VertexType vexs[MAXVEX]; //顶点集
EdgeType arc[MAXVEX][MAXVEX]; //边集
int numVertexes,numEdges;//图中的顶点数和边数
}MGraph;
//建立一个无向网图的邻接矩阵表示
void CreateMGraph(MGraph *G)
{
int i,j,k,w;
char T;
printf("请输入需建立图的顶点数和边数:\n");
scanf("%d%d",&G->numVertexes,&G->numEdges);
scanf("%c",&T);
for(i=0;i<G->numVertexes;i++)
scanf("%c",&G->vexs[i]);
for(i=0;i<G->numVertexes;i++)
for(j=0;j<G->numVertexes;j++)
{
G->arc[i][j]=INFINITY;
if(i==j)
G->arc[i][j]=0;
}
for(k=0;k<G->numEdges;k++)
{
printf("输入边的下标i和下标j:\n");
scanf("%d%d",&i,&j);
printf("请输入边(vi,vj)上的权w的值:\n");
scanf("%d",&w);
G->arc[i][j]=w;
G->arc[j][i]=w;//因为是无向图,矩阵对称
}
}
int main()
{
MGraph G;
int i,j;
CreateMGraph(&G);
//打印二维数组,可观察到此图的信息
for(i=0;i<G.numVertexes;i++)
{
for(j=0;j<G.numVertexes;j++)
printf("%7d ",G.arc[i][j]);
printf("\n");
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)