图->存储结构->数组表示法(邻接矩阵)

文字描述

　　用两个数组分别存储顶点信息和边/弧信息。

示意图

算法分析

　　构造一个采用邻接矩阵作存储结构、具有n个顶点和e条边的无向网(图)G的时间复杂度是(n*n + e*n), 其中对邻接矩阵G.arcs的初始化耗费了n*n的时间。

　　借助于邻接矩阵容易判定两个顶点之间是否有边/弧相连，并容易求得各个顶点的度。对于无向图，顶点vi的度是邻接矩阵地i行(或第i列)的元素之和；对于有向图，第i行的元素之和为顶点vi的出度；第j列的元素之和为顶点vj的入度；

代码实现

  1 /*
  2     以数组表示法(邻接矩阵)作为图的存储结构创建图。
  3 */
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 #include <string.h>
  7 
  8 #define INFINITY        100000    //最大值
  9 #define MAX_VERTEX_NUM    20        //最大顶点数
 10 typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网}
 11 typedef int  VRType;
 12 typedef char VertexType;
 13 typedef struct{
 14     char note[10];
 15 }InfoType;
 16 typedef struct ArcCell{
 17     VRType adj;        //顶点关系类型：1)对无权图，用1或0表示相邻否；2)对带权图，则为权值类型
 18     InfoType *info;    //该弧相关信息的指针
 19 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 20 typedef struct{
 21     VertexType vexs[MAX_VERTEX_NUM];    //顶点向量
 22     AdjMatrix arcs;        //邻接矩阵
 23     int vexnum, arcnum;    //图的当前顶点数和弧数
 24     GraphKind kind;        //图的种类标志
 25 }MGraph;
 26 
 27 /*
 28     若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。
 29 */
 30 int LocateVex(MGraph G, VertexType v){
 31     int i = 0;
 32     for(i=0; i<G.vexnum; i++){
 33         if(G.vexs[i] == v){
 34             return i;
 35         }
 36     }
 37     return -1;
 38 }
 39 
 40 /*
 41     采用数组表示法(邻接矩阵)，构造无向网
 42 */
 43 int CreateUDN(MGraph *G){
 44     int i = 0, j = 0, k = 0, IncInfo = 0;
 45     int v1 = 0, v2 = 0, w = 0;
 46     char tmp[10] = {0};
 47 
 48     printf("输入顶点数，弧数，其他信息标志位: ");
 49     scanf("%d,%d,%d", &G->vexnum, &G->arcnum, &IncInfo);
 50 
 51     for(i=0; i<G->vexnum; i++){
 52         printf("input vexs %d: ", i+1);
 53         memset(tmp, 0, sizeof(tmp));
 54         scanf("%s", tmp);
 55         G->vexs[i] = tmp[0];
 56     }
 57     for(i=0; i<G->vexnum; i++){
 58         for(j=0; j<G->vexnum; j++){
 59             G->arcs[i][j].adj = INFINITY;
 60             G->arcs[i][j].info = NULL;
 61         }
 62     }
 63     for(k=0; k<G->arcnum; k++){
 64         printf("输入第%d条弧: 顶点1, 顶点2，权值", k+1);
 65         memset(tmp, 0, sizeof(tmp));
 66         scanf("%s", tmp);
 67         sscanf(tmp, "%c,%c,%d", &v1, &v2, &w);
 68         i = LocateVex(*G, v1);
 69         j = LocateVex(*G, v2);
 70         G->arcs[i][j].adj = w;
 71         if(IncInfo){
 72             //
 73         }
 74         G->arcs[j][i] = G->arcs[i][j];
 75     }
 76     return 0;
 77 }
 78 
 79 /*
 80     采用数组表示法(邻接矩阵)，构造无向图
 81 */
 82 int CreateUDG(MGraph *G)
 83 {
 84     int i = 0, j = 0, k = 0, IncInfo = 0;
 85     int v1 = 0, v2 = 0, w = 0;
 86     char tmp[10] = {0};
 87 
 88     printf("输入顶点数，弧数，其他信息标志位: ");
 89     scanf("%d,%d,%d", &G->vexnum, &G->arcnum, &IncInfo);
 90 
 91     for(i=0; i<G->vexnum; i++){
 92         printf("输入第%d个顶点: ", i+1);
 93         memset(tmp, 0, sizeof(tmp));
 94         scanf("%s", tmp);
 95         G->vexs[i] = tmp[0];
 96     }
 97     for(i=0; i<G->vexnum; i++){
 98         for(j=0; j<G->vexnum; j++){
 99             G->arcs[i][j].adj = 0;
100             G->arcs[i][j].info = NULL;
101         }
102     }
103     for(k=0; k<G->arcnum; k++){
104         printf("输入第%d条弧(顶点1, 顶点2): ", k+1);
105         memset(tmp, 0, sizeof(tmp));
106         scanf("%s", tmp);
107         sscanf(tmp, "%c,%c", &v1, &v2, &w);
108         i = LocateVex(*G, v1);
109         j = LocateVex(*G, v2);
110         G->arcs[i][j].adj = 1;
111         if(IncInfo){
112             //
113         }
114         G->arcs[j][i] = G->arcs[i][j];
115     }
116     return 0;
117 }
118 
119 /*
120     采用数组表示法(邻接矩阵)，构造图
121 */
122 int CreateGraph(MGraph *G)
123 {
124     printf("输入图类型: -有向图(0), -有向网(1), +无向图(2), +无向网(3): ");
125     scanf("%d", &G->kind);
126     switch(G->kind){
127         case DG://构造有向图
128         case DN://构造有向网
129             printf("还不支持!
");
130             return -1;
131         case UDG://构造无向图
132             return CreateUDG(G);
133         case UDN://构造无向网
134             return CreateUDN(G);
135         default:
136             return -1;
137     }
138 }
139 
140 /*
141     输出图的信息
142 */
143 void printG(MGraph G)
144 {
145     if(G.kind == DG){
146         printf("类型：有向图；顶点数 %d, 弧数 %d
", G.vexnum, G.arcnum);
147     }else if(G.kind == DN){
148         printf("类型：有向网；顶点数 %d, 弧数 %d
", G.vexnum, G.arcnum);
149     }else if(G.kind == UDG){
150         printf("类型：无向图；顶点数 %d, 弧数 %d
", G.vexnum, G.arcnum);
151     }else if(G.kind == UDN){
152         printf("类型：无向网；顶点数 %d, 弧数 %d
", G.vexnum, G.arcnum);
153     }
154     int i = 0, j = 0;
155     printf("	");
156     for(i=0; i<G.vexnum; i++){
157         printf("%c	", G.vexs[i]);
158     }
159     printf("
");
160     for(i=0; i<G.vexnum; i++){
161         printf("%c	", G.vexs[i]);
162         for(j=0; j<G.vexnum; j++){
163             if(G.arcs[i][j].adj == INFINITY){
164                 printf("INF	");
165             }else{
166                 printf("%d	", G.arcs[i][j].adj);
167             }
168         }
169         printf("
");
170     }
171 }
172 
173 int main(int argc, char *argv[])
174 {
175     MGraph G;
176     if(CreateGraph(&G) > -1)
177         printG(G);
178     return 0;
179 }

邻接矩阵存储结构(图)

代码运行