所谓“邻接矩阵”的存储方式就是用一个一维数组存储图中全部的n个顶点的信息,用一个n×n的矩阵表示图中各顶点的邻接关系和权值。在矩阵中用1或0表示顶点间是否存在邻接关系。如果是网图的话,用0或∞表示不邻接(0可能被用作权值),用一个非零数表示权值。 根据图和矩阵的性质,该存储方式应具有以下特点:
无向图的邻接矩阵一定是一个对称阵,所以在存储时只需存储矩阵的上三角即可。由于这里讨论的是简单图,所以图中不存在自回路,所以矩阵的主对角线元素都为0。对于无向图,矩阵第i行(或第i列)的非零元素个数正好是第i个顶点的度。对于有向图,矩阵第i行(或第i列)的非零元素个数正好是第i个顶点的出度(或入度)。
下面给出邻接矩阵存储图的代码描述。
以下是存储结构的声明。
#define MaxVertexNum 100 //最大顶点数设为100
#define INFINITY 65535 //无穷设为双字节无符号整数的最大值65535
enum GraphType {DG, UG, DN, UN}; //有向图,无向图,有向网图,无向网图
typedef stuct Mgraph{
char Vertices[MaxVertexNum]; //顶点表
int Edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵,即边表
int n,e; //顶点数n,边数e
enum GraphType GType; //图的类型分为四种:DG,UG,DN,UN
}* MGraph; //MGraph是以邻接矩阵存储的图类型
下面以无向图为例给出初始化算法。
MGraph CreateMGraph()
{
MGraph G;
int w;
G = (MGraph)malloc(sizeof(struct Mgaph));
G->Gtype = UN;
printf("输入定点数和边数(格式:顶点数,边数):\n");
scanf("%d,%d",&(G->n),&(G->e));
printf("输入顶点信息(用空格隔开):\n");
for(int i = 0; i < G->n; i++){
scanf("%c",&G->Vertices[i]);
getchar();
}
for(int i = 0; i < G->n; i++)
for(int j = 0; j < G->n; j++)
G->Edges[i][j] = INFINITY; //初始化邻接矩阵
printf("输入每条边对应的两个顶点的序号和权值(格式:i,j,w):\n");
for(int i, j, k = 0; k < G->e; k++){
scanf("%d,%d,%d", &i,&j,&w);
G->Edges[i][j] = w;
G->Edges[j][i] = w;
}
return G;
}
|