本博文是是博主在学习数据结构图的这一章知识时做的一些总结，代码运行环境：visual studio2017 纯C语言 ，当然掌握了方法，你也可以试着用其它的语言来实现同样的功能。
下面的程序主要实现了对有向图，有向网，无向图，无向网，无向图的深度优先遍历，广度优先遍历，有向无环图的拓扑排序功能等。
主要代码实现如下：
1 #pragma once
2 #include<stdio.h>
3 #include"stdlib.h"
4 #define ElemType char
5 #define MAXQSIZE 50
6 #define INFINITY INT_MAX
7 #define MAX_VERTEX_NUM 20
8 typedef enum { DG, DN, UDG, UDN } GraphKind;
9 typedef struct ArcCell {
10 int adj; //顶点关系类型 对于无权图 用0或1表示
11 //char *info; //弧相关信息的指针
12 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
13 typedef struct {
14 char vers[MAX_VERTEX_NUM]; //用一个字符数组存储顶点向量
15 AdjMatrix arcs; //邻接矩阵
16 int vexnum, arcnum; //图的当前顶点数和弧数
17 GraphKind kind; //图的种类标志
18 int in[MAX_VERTEX_NUM]; //存放所有节点的入度
19 }MGraph;
20 //图G中顶点v的第一个邻接点，不存在时返回 -1
21 int FirstAdjVex(MGraph&G, int v)
22 {
23
24 int i;
25 for (i = 0; i < G.vexnum; i++)
26 {
27 if (G.arcs[v][i].adj)
28 {
29 return i;
30 }
31 }
32 return -1;
33 }
34 //图G中顶点v在w之后的下一个邻接点，不存在时返回 -1
35 int NextAdjVex(MGraph G, int v, int w)
36 {
37
38 int i;
39 for (i = w + 1; i < G.vexnum; i++)
40 {
41 if (G.arcs[v][i].adj)
42 {
43 return i;
44 }
45 }
46 return -1;
47
48 }
49 //深度优先遍历图
50 bool visited[MAX_VERTEX_NUM];
51 void DFS(MGraph G, int v)
52 {
53 visited[v] = true;
54 printf("%c", G.vers[v]);
55 int j;
56 for (j = 1; j <= G.vexnum; j++) {
57 if (visited[j] == 0 && G.arcs[v][j].adj == 1)
58 {
59 DFS(G, j);//v每循环一次值都会变 上一轮的j值赋给了v
60 }
61 }
62 }
63
64 //广度优先遍历
65 int BFSTraverse(MGraph G, int s)
66 {
67 //清空访问标志
68 for (int i = 0; i <MAX_VERTEX_NUM; i++)
69 visited[i] = false;
70 //定义队列，用于保存当前节点的邻接顶点
71 int Q[MAX_VERTEX_NUM];
72 int front = 0;
73 int rear = 0;
74 int i, j;
75 printf("%c", G.vers[s]);
76 visited[s] = 1;
77 Q[rear++] = s;
78 //遍历队列
79 while (front < rear)
80 {
81 i = Q[front++];
82 for (j = 1; j <= G.vexnum; j++)
83 {
84 if (visited[j] == false && G.arcs[i][j].adj == 1)
85 {
86 printf("%c", G.vers[j]);
87 visited[j] = true;
88 Q[rear++] = j;
89 }
90
91 }
92 }
93 return 0;
94 }
95
96 //定位顶点
97 int LocateVex(MGraph &G, char v)
98 {
99 int i;
100 for (i = 0; i<G.vexnum; i++)
101 {
102 if (v == G.vers[i])
103 {
104 return i;
105 }
106 }
107 return -1;
108
109 }
110
111 //创建有向图
112 int CreateDG(MGraph &G) {
113 int i, j, k;
114 char v1, v2;
115 printf("请输入顶点数:");
116 scanf("%d", &G.vexnum);
117 printf("\n请输入弧数:");
118 scanf("%d", &G.arcnum);
119 printf("请输入%d个顶点：(每个顶点之间用空格隔开)", G.vexnum);
120 fflush(stdin);
121 getchar(); //吃掉空格
122 for (i = 0; i < G.vexnum; i++)
123 {
124 scanf("%c", &G.vers[i]);
125 getchar(); //吃掉空格 注意数组vers[i]的初始大小为20
126 }
127 //打印输出各个顶点
128 for (i = 0; i < G.vexnum; i++)
129 {
130 printf("%c", G.vers[i]);
131
132 }
133 printf("\n");
134 for (i = 0; i < G.vexnum; i++)
135 {
136 for (j = 0; j < G.vexnum; j++)
137 {
138 G.arcs[i][j].adj = INFINITY;
139
140 }
141 }
142 //入度初始化
143 for (int i = 0; i < G.vexnum; i++)
144 {
145 G.in[i] = 0;
146 }
147 for (k = 0; k < G.arcnum; k++)
148 {
149 printf("\nplease input <v1 v2>:");
150 fflush(stdin);
151 scanf("%c %c", &v1, &v2); //v1 v2 之间用空格隔开
152 fflush(stdin);//清除残余后，后面再读入时不会出错
153 i = LocateVex(G, v1);
154 j = LocateVex(G, v2);
155 G.arcs[i][j].adj = 1;
156 G.in[j]++;
157 getchar();
158 }
159 return 1;
160 }
161
162 //创建有向网
163 int CreateDN(MGraph &G) {
164 int i, j, k, w;
165 char v1, v2;
166 printf("请输入顶点数：");
167 scanf("%d", &G.vexnum);
168 printf("\n请输入弧的数目:");
169 scanf("%d", &G.arcnum);
170 printf("请输入%d个顶点：(每个顶点之间用空格隔开)", G.vexnum);
171 fflush(stdin);
172 getchar(); //吃掉空格
173 for (i = 0; i < G.vexnum; i++)
174 {
175 scanf("%c", &G.vers[i]);
176 getchar(); //吃掉空格 注意数组vers[i]的初始大小为20
177 }
178 //打印输出各个顶点
179 for (i = 0; i < G.vexnum; i++)
180 {
181 printf("%c", G.vers[i]);
182
183 }
184 printf("\n");
185 //初始化邻接矩阵
186 for (i = 0; i < G.vexnum; i++)
187 {
188 for (j = 0; j < G.vexnum; j++)
189 {
190 G.arcs[i][j].adj = INFINITY;
191
192 }
193 }
194 for (k = 0; k < G.arcnum; k++)
195 {
196 printf("\n please input <v1 v2 w>:");
197 fflush(stdin);
198 scanf("%c %c %d", &v1, &v2, &w); //v1 v2 w之间用空格隔开
199 fflush(stdin);//清除残余后，后面再读入时不会出错
200 i = LocateVex(G, v1);
201 j = LocateVex(G, v2);
202 G.arcs[i][j].adj = w;
203
204 getchar(); //吃掉空格
205 }
206 return 1;
207 }
208
209 //创建无向图
210 int CreateUDG(MGraph &G)
211 {
212 int i, j, k;
213 char v1, v2;
214 printf("请输入顶点数:");
215 scanf("%d", &G.vexnum);
216 printf("\n请输入边数:");
217 scanf("%d", &G.arcnum);
218 printf("请输入%d个顶点：(每个顶点之间用空格隔开)", G.vexnum);
219 fflush(stdin);
220 getchar(); //吃掉空格
221 for (i = 0; i < G.vexnum; i++)
222 {
223 scanf("%c", &G.vers[i]);
224 getchar(); //吃掉空格 注意数组vers[i]的初始大小为20
225 }
226 //打印输出各个顶点
227 for (i = 0; i < G.vexnum; i++)
228 {
229 printf("%c", G.vers[i]);
230
231 }
232 printf("\n");
233 for (i = 0; i < G.vexnum; i++)
234 {
235 for (j = 0; j < G.vexnum; j++)
236 {
237 G.arcs[i][j].adj = INFINITY;
238 }
239 }
240 for (k = 0; k < G.arcnum; k++)
241 {
242 printf("\nplease input <v1 v2>:");
243 fflush(stdin);
244 scanf("%c %c", &v1, &v2); //v1 v2 之间用空格隔开
245 fflush(stdin);//清除残余后，后面再读入时不会出错
246 i = LocateVex(G, v1);
247 j = LocateVex(G, v2);
248 G.arcs[i][j].adj = 1;
249 G.arcs[j][i].adj = 1;
250 getchar();
251 }
252 return 1;
253 }
254
255 //创建无向网
256 int CreateUDN(MGraph &G)
257 {
258 int i, j, k, w;
259 char v1, v2;
260 printf("请输入顶点数：");
261 scanf("%d", &G.vexnum);
262 printf("\n请输入边的数目:");
263 scanf("%d", &G.arcnum);
264 printf("请输入%d个顶点：(每个顶点之间用空格隔开)", G.vexnum);
265 fflush(stdin);
266 getchar(); //吃掉空格
267 for (i = 0; i < G.vexnum; i++)
268 {
269 scanf("%c", &G.vers[i]);
270 getchar(); //吃掉空格 注意数组vers[i]的初始大小为20
271 }
272 //打印输出各个顶点
273 for (i = 0; i < G.vexnum; i++)
274 {
275 printf("%c", G.vers[i]);
276
277 }
278 printf("\n");
279 //初始化邻接矩阵
280 for (i = 0; i < G.vexnum; i++)
281 {
282 for (j = 0; j < G.vexnum; j++)
283 {
284 G.arcs[i][j].adj = INFINITY;
285 }
286 }
287 for (k = 0; k < G.arcnum; k++)
288 {
289 printf("\n please input <v1 v2 w>:");
290 fflush(stdin);
291 scanf("%c %c %d", &v1, &v2, &w); //v1 v2 w之间用空格隔开
292 fflush(stdin);//清除残余后，后面再读入时不会出错
293 i = LocateVex(G, v1);
294 j = LocateVex(G, v2);
295 G.arcs[i][j].adj = w;
296 G.arcs[j][i].adj = w;
297 getchar(); //吃掉空格
298 }
299 return 1;
300 }
301 //栈类型
302 typedef int SElemType;
303 #define STACK_INIT_SIZE1 10 //存储空间初始分配量
304 #define STACKINCREMENT1 2 //存储空间分配增量
305
306 //栈的顺序存储结构表示
307 typedef struct SqStack1
308 {
309 SElemType *base; //基地址
310 SElemType *top; //栈顶指针
311 int stacksize1; //当前已经分配的存储空间
312 }SqStack1;
313
314 //构造一个空栈
315 int InitStack1(SqStack1&S)
316 {
317 //为栈底分分配一个指定大小的存储空间
318 S.base = (SElemType *)malloc(STACK_INIT_SIZE1 * sizeof(SElemType));
319 if (!S.base)
320 exit(0);
321 S.top = S.base; //栈底与栈顶指针相同
322 S.stacksize1 = STACK_INIT_SIZE1;
323 return 1;
324 }
325
326
327 //若栈S为空栈（栈底指针和栈顶指针相同）, 则返回1，否则返回0
328 int StackEmpty1(SqStack1&S)
329 {
330 if (S.top == S.base)
331 return 1;
332 else
333 return 0;
334 }
335
336
337 //插入元素e为新的栈顶元素
338 int Push(SqStack1 *S, SElemType e)
339 {
340 if ((*S).top - (*S).base >= (*S).stacksize1)
341 {
342 (*S).base = (SElemType *)realloc((*S).base, ((*S).stacksize1 + STACKINCREMENT1) * sizeof(SElemType));
343 if (!(*S).base)
344 exit(0);
345 (*S).top = (*S).base + (*S).stacksize1;
346 (*S).stacksize1 += STACKINCREMENT1;
347 }
348 *((*S).top)++ = e;
349 return 1;
350 }
351
352
353 //若栈不为空，则删除S栈顶元素用e返回其值，并返回1，否则返回0
354 int Pop(SqStack1 *S, SElemType *e)
355 {
356 if ((*S).top == (*S).base)
357 {
358 return 0;
359 }
360 *e = *--(*S).top;
361 return 1;
362 }
363 //有向图的拓扑排序
364 void TopologicalSort(MGraph G)
365 {
366 int i, j,k;
367 int count = 0;
368 SqStack1 S;
369 InitStack1(S);
370 for (i = 0; i<G.vexnum; i++)
371 {
372 if (G.in[i] == 0)
373 {
374 Push(&S, i);
375 }
376 }
377 while (!StackEmpty1(S))
378 {
379 Pop(&S, &k);
380 printf("%c->", G.vers[k]);
381 count++;
382 for (i = 0; i < G.vexnum; i++)
383 {
384 if (G.arcs[k][i].adj == 1)
385 {
386 G.in[i]--;
387 if (G.in[i] == 0)
388 {
389 Push(&S, i);
390 }
391 }
392 }
393 }
394 //如果计算得到的拓扑排序的节点数目小于总的，说明不是连通图
395 if (count < G.vexnum)
396 {
397 printf("此图是有环路的\n");
398 }
399 else
400 {
401 printf("此图是没有环路的\n");
402 }
403
404 }
