文字描述
用两个数组分别存储顶点信息和边/弧信息。
示意图
算法分析
构造一个采用邻接矩阵作存储结构、具有n个顶点和e条边的无向网(图)G的时间复杂度是(n*n + e*n), 其中对邻接矩阵G.arcs的初始化耗费了n*n的时间。
借助于邻接矩阵容易判定两个顶点之间是否有边/弧相连，并容易求得各个顶点的度。对于无向图，顶点vi的度是邻接矩阵地i行(或第i列)的元素之和；对于有向图，第i行的元素之和为顶点vi的出度；第j列的元素之和为顶点vj的入度；
代码实现
/*
以数组表示法(邻接矩阵)作为图的存储结构创建图。
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h> #define INFINITY 100000 //最大值
#define MAX_VERTEX_NUM 20 //最大顶点数
typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网}
typedef int VRType;
typedef char VertexType;
typedef struct{
char note[];
}InfoType;
typedef struct ArcCell{
VRType adj; //顶点关系类型：1)对无权图，用1或0表示相邻否；2)对带权图，则为权值类型
InfoType *info; //该弧相关信息的指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum, arcnum; //图的当前顶点数和弧数
GraphKind kind; //图的种类标志
}MGraph; /*
若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。
*/
int LocateVex(MGraph G, VertexType v){
int i = ;
for(i=; i<G.vexnum; i++){
if(G.vexs[i] == v){
return i;
}
}
return -;
} /*
采用数组表示法(邻接矩阵)，构造无向网
*/
int CreateUDN(MGraph *G){
int i = , j = , k = , IncInfo = ;
int v1 = , v2 = , w = ;
char tmp[] = {}; printf("输入顶点数，弧数，其他信息标志位: ");
scanf("%d,%d,%d", &G->vexnum, &G->arcnum, &IncInfo); for(i=; i<G->vexnum; i++){
printf("input vexs %d: ", i+);
memset(tmp, , sizeof(tmp));
scanf("%s", tmp);
G->vexs[i] = tmp[];
}
for(i=; i<G->vexnum; i++){
for(j=; j<G->vexnum; j++){
G->arcs[i][j].adj = INFINITY;
G->arcs[i][j].info = NULL;
}
}
for(k=; k<G->arcnum; k++){
printf("输入第%d条弧: 顶点1, 顶点2，权值", k+);
memset(tmp, , sizeof(tmp));
scanf("%s", tmp);
sscanf(tmp, "%c,%c,%d", &v1, &v2, &w);
i = LocateVex(*G, v1);
j = LocateVex(*G, v2);
G->arcs[i][j].adj = w;
if(IncInfo){
//
}
G->arcs[j][i] = G->arcs[i][j];
}
return ;
} /*
采用数组表示法(邻接矩阵)，构造无向图
*/
int CreateUDG(MGraph *G)
{
int i = , j = , k = , IncInfo = ;
int v1 = , v2 = , w = ;
char tmp[] = {}; printf("输入顶点数，弧数，其他信息标志位: ");
scanf("%d,%d,%d", &G->vexnum, &G->arcnum, &IncInfo); for(i=; i<G->vexnum; i++){
printf("输入第%d个顶点: ", i+);
memset(tmp, , sizeof(tmp));
scanf("%s", tmp);
G->vexs[i] = tmp[];
}
for(i=; i<G->vexnum; i++){
for(j=; j<G->vexnum; j++){
G->arcs[i][j].adj = ;
G->arcs[i][j].info = NULL;
}
}
for(k=; k<G->arcnum; k++){
printf("输入第%d条弧(顶点1, 顶点2): ", k+);
memset(tmp, , sizeof(tmp));
scanf("%s", tmp);
sscanf(tmp, "%c,%c", &v1, &v2, &w);
i = LocateVex(*G, v1);
j = LocateVex(*G, v2);
G->arcs[i][j].adj = ;
if(IncInfo){
//
}
G->arcs[j][i] = G->arcs[i][j];
}
return ;
} /*
采用数组表示法(邻接矩阵)，构造图
*/
int CreateGraph(MGraph *G)
{
printf("输入图类型: -有向图(0), -有向网(1), +无向图(2), +无向网(3): ");
scanf("%d", &G->kind);
switch(G->kind){
case DG://构造有向图
case DN://构造有向网
printf("还不支持!\n");
return -;
case UDG://构造无向图
return CreateUDG(G);
case UDN://构造无向网
return CreateUDN(G);
default:
return -;
}
} /*
输出图的信息
*/
void printG(MGraph G)
{
if(G.kind == DG){
printf("类型：有向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
}else if(G.kind == DN){
printf("类型：有向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
}else if(G.kind == UDG){
printf("类型：无向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
}else if(G.kind == UDN){
printf("类型：无向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
}
int i = , j = ;
printf("\t");
for(i=; i<G.vexnum; i++){
printf("%c\t", G.vexs[i]);
}
printf("\n");
for(i=; i<G.vexnum; i++){
printf("%c\t", G.vexs[i]);
for(j=; j<G.vexnum; j++){
if(G.arcs[i][j].adj == INFINITY){
printf("INF\t");
}else{
printf("%d\t", G.arcs[i][j].adj);
}
}
printf("\n");
}
} int main(int argc, char *argv[])
{
MGraph G;
if(CreateGraph(&G) > -)
printG(G);
return ;
}
邻接矩阵存储结构(图)
代码运行