本博文是是博主在学习数据结构图的这一章知识时做的一些总结，代码运行环境：visual studio2017 纯C语言 ，当然掌握了方法，你也可以试着用其它的语言来实现同样的功能。
下面的程序主要实现了对有向图，有向网，无向图，无向网，无向图的深度优先遍历，广度优先遍历，有向无环图的拓扑排序功能等。
主要代码实现如下：
1 1 #pragma once 2 2 #include<stdio.h> 3 3 #include"stdlib.h" 4 4 #define ElemType char 5 5 #define MAXQSIZE 50 6 6 #define INFINITY INT_MAX 7 7 #define MAX_VERTEX_NUM 20 8 8 typedef enum { DG, DN, UDG, UDN } GraphKind; 9 9 typedef struct ArcCell { 10 10 int adj; //顶点关系类型 对于无权图 用0或1表示 11 11 //char *info; //弧相关信息的指针 12 12 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 13 13 typedef struct { 14 14 char vers[MAX_VERTEX_NUM]; //用一个字符数组存储顶点向量 15 15 AdjMatrix arcs; //邻接矩阵 16 16 int vexnum, arcnum; //图的当前顶点数和弧数 17 17 GraphKind kind; //图的种类标志 18 18 int in[MAX_VERTEX_NUM]; //存放所有节点的入度 19 19 }MGraph; 20 20 //图G中顶点v的第一个邻接点，不存在时返回 -1 21 21 int FirstAdjVex(MGraph&G, int v) 22 22 { 23 23 24 24 int i; 25 25 for (i = 0; i < G.vexnum; i++) 26 26 { 27 27 if (G.arcs[v][i].adj) 28 28 { 29 29 return i; 30 30 } 31 31 } 32 32 return -1; 33 33 } 34 34 //图G中顶点v在w之后的下一个邻接点，不存在时返回 -1 35 35 int NextAdjVex(MGraph G, int v, int w) 36 36 { 37 37 38 38 int i; 39 39 for (i = w + 1; i < G.vexnum; i++) 40 40 { 41 41 if (G.arcs[v][i].adj) 42 42 { 43 43 return i; 44 44 } 45 45 } 46 46 return -1; 47 47 48 48 } 49 49 //深度优先遍历图 50 50 bool visited[MAX_VERTEX_NUM]; 51 51 void DFS(MGraph G, int v) 52 52 { 53 53 visited[v] = true; 54 54 printf("%c", G.vers[v]); 55 55 int j; 56 56 for (j = 1; j <= G.vexnum; j++) { 57 57 if (visited[j] == 0 && G.arcs[v][j].adj == 1) 58 58 { 59 59 DFS(G, j);//v每循环一次值都会变 上一轮的j值赋给了v 60 60 } 61 61 } 62 62 } 63 63 64 64 //广度优先遍历 65 65 int BFSTraverse(MGraph G, int s) 66 66 { 67 67 //清空访问标志 68 68 for (int i = 0; i <MAX_VERTEX_NUM; i++) 69 69 visited[i] = false; 70 70 //定义队列，用于保存当前节点的邻接顶点 71 71 int Q[MAX_VERTEX_NUM]; 72 72 int front = 0; 73 73 int rear = 0; 74 74 int i, j; 75 75 printf("%c", G.vers[s]); 76 76 visited[s] = 1; 77 77 Q[rear++] = s; 78 78 //遍历队列 79 79 while (front < rear) 80 80 { 81 81 i = Q[front++]; 82 82 for (j = 1; j <= G.vexnum; j++) 83 83 { 84 84 if (visited[j] == false && G.arcs[i][j].adj == 1) 85 85 { 86 86 printf("%c", G.vers[j]); 87 87 visited[j] = true; 88 88 Q[rear++] = j; 89 89 } 90 90 91 91 } 92 92 } 93 93 return 0; 94 94 } 95 95 96 96 //定位顶点 97 97 int LocateVex(MGraph &G, char v) 98 98 { 99 99 int i; 100100 for (i = 0; i<G.vexnum; i++) 101101 { 102102 if (v == G.vers[i]) 103103 { 104104 return i; 105105 } 106106 } 107107 return -1; 108108 109109 } 110110 111111 //创建有向图 112112 int CreateDG(MGraph &G) { 113113 int i, j, k; 114114 char v1, v2; 115115 printf("请输入顶点数:"); 116116 scanf("%d", &G.vexnum); 117117 printf("\n请输入弧数:"); 118118 scanf("%d", &G.arcnum); 119119 printf("请输入%d个顶点：(每个顶点之间用空格隔开)", G.vexnum); 120120 fflush(stdin); 121121 getchar(); //吃掉空格 122122 for (i = 0; i < G.vexnum; i++) 123123 { 124124 scanf("%c", &G.vers[i]); 125125 getchar(); //吃掉空格 注意数组vers[i]的初始大小为20 126126 } 127127 //打印输出各个顶点 128128 for (i = 0; i < G.vexnum; i++) 129129 { 130130 printf("%c", G.vers[i]); 131131 132132 } 133133 printf("\n"); 134134 for (i = 0; i < G.vexnum; i++) 135135 { 136136 for (j = 0; j < G.vexnum; j++) 137137 { 138138 G.arcs[i][j].adj = INFINITY; 139139 140140 } 141141 } 142142 //入度初始化 143143 for (int i = 0; i < G.vexnum; i++) 144144 { 145145 G.in[i] = 0; 146146 } 147147 for (k = 0; k < G.arcnum; k++) 148148 { 149149 printf("\nplease input <v1 v2>:"); 150150 fflush(stdin); 151151 scanf("%c %c", &v1, &v2); //v1 v2 之间用空格隔开 152152 fflush(stdin);//清除残余后，后面再读入时不会出错 153153 i = LocateVex(G, v1); 154154 j = LocateVex(G, v2); 155155 G.arcs[i][j].adj = 1; 156156 G.in[j]++; 157157 getchar(); 158158 } 159159 return 1; 160160 } 161161 162162 //创建有向网 163163 int CreateDN(MGraph &G) { 164164 int i, j, k, w; 165165 char v1, v2; 166166 printf("请输入顶点数："); 167167 scanf("%d", &G.vexnum); 168168 printf("\n请输入弧的数目:"); 169169 scanf("%d", &G.arcnum); 170170 printf("请输入%d个顶点：(每个顶点之间用空格隔开)", G.vexnum); 171171 fflush(stdin); 172172 getchar(); //吃掉空格 173173 for (i = 0; i < G.vexnum; i++) 174174 { 175175 scanf("%c", &G.vers[i]); 176176 getchar(); //吃掉空格 注意数组vers[i]的初始大小为20 177177 } 178178 //打印输出各个顶点 179179 for (i = 0; i < G.vexnum; i++) 180180 { 181181 printf("%c", G.vers[i]); 182182 183183 } 184184 printf("\n"); 185185 //初始化邻接矩阵 186186 for (i = 0; i < G.vexnum; i++) 187187 { 188188 for (j = 0; j < G.vexnum; j++) 189189 { 190190 G.arcs[i][j].adj = INFINITY; 191191 192192 } 193193 } 194194 for (k = 0; k < G.arcnum; k++) 195195 { 196196 printf("\n please input <v1 v2 w>:"); 197197 fflush(stdin); 198198 scanf("%c %c %d", &v1, &v2, &w); //v1 v2 w之间用空格隔开 199199 fflush(stdin);//清除残余后，后面再读入时不会出错 200200 i = LocateVex(G, v1); 201201 j = LocateVex(G, v2); 202202 G.arcs[i][j].adj = w; 203203 204204 getchar(); //吃掉空格 205205 } 206206 return 1; 207207 } 208208 209209 //创建无向图 210210 int CreateUDG(MGraph &G) 211211 { 212212 int i, j, k; 213213 char v1, v2; 214214 printf("请输入顶点数:"); 215215 scanf("%d", &G.vexnum); 216216 printf("\n请输入边数:"); 217217 scanf("%d", &G.arcnum); 218218 printf("请输入%d个顶点：(每个顶点之间用空格隔开)", G.vexnum); 219219 fflush(stdin); 220220 getchar(); //吃掉空格 221221 for (i = 0; i < G.vexnum; i++) 222222 { 223223 scanf("%c", &G.vers[i]); 224224 getchar(); //吃掉空格 注意数组vers[i]的初始大小为20 225225 } 226226 //打印输出各个顶点 227227 for (i = 0; i < G.vexnum; i++) 228228 { 229229 printf("%c", G.vers[i]); 230230 231231 } 232232 printf("\n"); 233233 for (i = 0; i < G.vexnum; i++) 234234 { 235235 for (j = 0; j < G.vexnum; j++) 236236 { 237237 G.arcs[i][j].adj = INFINITY; 238238 } 239239 } 240240 for (k = 0; k < G.arcnum; k++) 241241 { 242242 printf("\nplease input <v1 v2>:"); 243243 fflush(stdin); 244244 scanf("%c %c", &v1, &v2); //v1 v2 之间用空格隔开 245245 fflush(stdin);//清除残余后，后面再读入时不会出错 246246 i = LocateVex(G, v1); 247247 j = LocateVex(G, v2); 248248 G.arcs[i][j].adj = 1; 249249 G.arcs[j][i].adj = 1; 250250 getchar(); 251251 } 252252 return 1; 253253 } 254254 255255 //创建无向网 256256 int CreateUDN(MGraph &G) 257257 { 258258 int i, j, k, w; 259259 char v1, v2; 260260 printf("请输入顶点数："); 261261 scanf("%d", &G.vexnum); 262262 printf("\n请输入边的数目:"); 263263 scanf("%d", &G.arcnum); 264264 printf("请输入%d个顶点：(每个顶点之间用空格隔开)", G.vexnum); 265265 fflush(stdin); 266266 getchar(); //吃掉空格 267267 for (i = 0; i < G.vexnum; i++) 268268 { 269269 scanf("%c", &G.vers[i]); 270270 getchar(); //吃掉空格 注意数组vers[i]的初始大小为20 271271 } 272272 //打印输出各个顶点 273273 for (i = 0; i < G.vexnum; i++) 274274 { 275275 printf("%c", G.vers[i]); 276276 277277 } 278278 printf("\n"); 279279 //初始化邻接矩阵 280280 for (i = 0; i < G.vexnum; i++) 281281 { 282282 for (j = 0; j < G.vexnum; j++) 283283 { 284284 G.arcs[i][j].adj = INFINITY; 285285 } 286286 } 287287 for (k = 0; k < G.arcnum; k++) 288288 { 289289 printf("\n please input <v1 v2 w>:"); 290290 fflush(stdin); 291291 scanf("%c %c %d", &v1, &v2, &w); //v1 v2 w之间用空格隔开 292292 fflush(stdin);//清除残余后，后面再读入时不会出错 293293 i = LocateVex(G, v1); 294294 j = LocateVex(G, v2); 295295 G.arcs[i][j].adj = w; 296296 G.arcs[j][i].adj = w; 297297 getchar(); //吃掉空格 298298 } 299299 return 1; 300300 } 301301 //栈类型 302302 typedef int SElemType; 303303 #define STACK_INIT_SIZE1 10 //存储空间初始分配量 304304 #define STACKINCREMENT1 2 //存储空间分配增量 305305 306306 //栈的顺序存储结构表示 307307 typedef struct SqStack1 308308 { 309309 SElemType *base; //基地址 310310 SElemType *top; //栈顶指针 311311 int stacksize1; //当前已经分配的存储空间 312312 }SqStack1; 313313 314314 //构造一个空栈 315315 int InitStack1(SqStack1&S) 316316 { 317317 //为栈底分分配一个指定大小的存储空间 318318 S.base = (SElemType *)malloc(STACK_INIT_SIZE1 * sizeof(SElemType)); 319319 if (!S.base) 320320 exit(0); 321321 S.top = S.base; //栈底与栈顶指针相同 322322 S.stacksize1 = STACK_INIT_SIZE1; 323323 return 1; 324324 } 325325 326326 327327 //若栈S为空栈（栈底指针和栈顶指针相同）, 则返回1，否则返回0 328328 int StackEmpty1(SqStack1&S) 329329 { 330330 if (S.top == S.base) 331331 return 1; 332332 else 333333 return 0; 334334 } 335335 336336 337337 //插入元素e为新的栈顶元素 338338 int Push(SqStack1 *S, SElemType e) 339339 { 340340 if ((*S).top - (*S).base >= (*S).stacksize1) 341341 { 342342 (*S).base = (SElemType *)realloc((*S).base, ((*S).stacksize1 + STACKINCREMENT1) * sizeof(SElemType)); 343343 if (!(*S).base) 344344 exit(0); 345345 (*S).top = (*S).base + (*S).stacksize1; 346346 (*S).stacksize1 += STACKINCREMENT1; 347347 } 348348 *((*S).top)++ = e; 349349 return 1; 350350 } 351351 352352 353353 //若栈不为空，则删除S栈顶元素用e返回其值，并返回1，否则返回0 354354 int Pop(SqStack1 *S, SElemType *e) 355355 { 356356 if ((*S).top == (*S).base) 357357 { 358358 return 0; 359359 } 360360 *e = *--(*S).top; 361361 return 1; 362362 } 363363 //有向图的拓扑排序 364364 void TopologicalSort(MGraph G) 365365 { 366366 int i, j,k; 367367 int count = 0; 368368 SqStack1 S; 369369 InitStack1(S); 370370 for (i = 0; i<G.vexnum; i++) 371371 { 372372 if (G.in[i] == 0) 373373 { 374374 Push(&S, i); 375375 } 376376 } 377377 while (!StackEmpty1(S)) 378378 { 379379 Pop(&S, &k); 380380 printf("%c->", G.vers[k]); 381381 count++; 382382 for (i = 0; i < G.vexnum; i++) 383383 { 384384 if (G.arcs[k][i].adj == 1) 385385 { 386386 G.in[i]--; 387387 if (G.in[i] == 0) 388388 { 389389 Push(&S, i); 390390 } 391391 } 392392 } 393393 } 394394 //如果计算得到的拓扑排序的节点数目小于总的，说明不是连通图 395395 if (count < G.vexnum) 396396 { 397397 printf("此图是有环路的\n"); 398398 } 399399 else 400400 { 401401 printf("此图是没有环路的\n"); 402402 } 403403 404404 }