图的基本算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了图的基本算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9377字，纯文字阅读大概需要14分钟。
内容图文
近两个星期，回顾数据结构时又把图的相关知识复习了一下，顺便为了提高编码能力，将基本算法也都实现了一下。现将实例附录如下：
1)要实现的算法
①建立图的存储结构
②深度优先搜索和广度优先搜索
③求图的最小生成树
④拓扑排序
⑤最短路径
2)存储结构设计
本系统采用图结构（mgraph）存储抽象操作的信息。其中，各结点间的邻接关系用图的邻接矩阵类型（adjmatrix）存储。顶点信息用结构数组（vexs）存储。其中每个数据元素师一个结构变量，包括一些基本信息。
此外，本系统还设置了三个全局变量：visited[]数组用于存储顶点是否被访问标记；d[]用于存放边上的权值或者是存储查找路径顶点的编号；campus是一个图结构的全局变量
3)功能设计
本程序一共设置了9个子功能菜单，图的初始化由函数initgraph（）实现，依据读入的图的顶点个数和边的个数。分别初始化图结构中图的顶点向量数组和图的邻接矩阵。9个功能设计描述如下：
①建立有向图。有向图的建立有由BuildAdjacencyList()实现。当用户选择该功能时，用户要手动输入该图的信息。从而建立有向图。
②输出邻接表。邻接表的输出有函数ShowAdjacencyList()实现。当用户选择该项功能时，系统即以邻接表的形式输出各顶点所连接的点。
③输出顶点的度。顶点读的输出由函数ShowAdjacencyListDegree()实现。当用户选择该功能时，系统即将每个顶点的度以数字的形式输出。
④进行拓扑排序。拓扑排序功能的实现由函数TopologicalSortAdjacencyList()完成。一旦选择，就会进行排序并输出。
⑤深度优先遍历。采用DFS算法进行深度优先遍历，遍历完成后，将遍历得到的结点有序输出。
⑥广度优先遍历。采用BFS算法进行广度优先遍历，遍历完成后，将遍历得到的结点有序输出。
⑦无向图最小生成树。最小生成树的算法实现由函数AdjacencyListPrim()完成。该函数采用Prim算法对邻接矩阵求最小生成树并输出。
⑧有向图求最短路径。最短路径的实现采用函数AdjacencyListDijkstra()完成。该函数采用的是Dijkstra 算法对邻接矩阵对各顶点到其他顶点的最短距离。并依次输出。
4)测试结果
①菜单界面
②建立有向图
③输出该邻接表
④输出顶点的度
⑤进行拓扑排序
⑥深度优先搜索
⑦广度优先搜索
⑧最短路径
5)源代码附录
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4#define MAX_VERTEX_NUM 100
5#define MAX 1000000000
6 typedef struct Arcnode /////邻接表除头结点以外的结点 7{
8int adjvex;
9struct Arcnode *nextarc;
10int weight;
11}ArcNode;
12 typedef struct Vnode /////邻接表的头结点 13{
14int data;
15struct Arcnode *fistarc;
16}Vnode;
17 Vnode AdjList[MAX_VERTEX_NUM]; ////有多个头结点，定义为数组形式了 18 19int flag[MAX_VERTEX_NUM];
20int count[MAX_VERTEX_NUM];
21int map[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; ///////无向图邻接矩阵 22int map2[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; ////////有向图的邻接矩阵 23int map3[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; ///////"临时"的邻接矩阵 24int topocount[MAX_VERTEX_NUM];
25int topoflag[MAX_VERTEX_NUM];
26int num[MAX_VERTEX_NUM]; /////用于存储深度优先遍历和广度优先遍历的结果 27 28int K; //////表示遍历过的节点数 29int choose; //////主菜单选择变量 30int Num,Number; //////Num表示顶点的个数，number表示的为边的个数 31 32 33void Build_VAdjacencyList() ///////建立并初始化头结点 34{
35int i;
36for(i=0;i<Num;i++)
37 {
38 AdjList[i].data=i+1;
39 AdjList[i].fistarc=NULL;
40 }
41}
42void BuildAdjacencyList() ///////////建立邻接表，当然，在建立邻接表的同时也建立了此图的图的有向图邻接矩阵以及无向图的邻接矩阵 43{
44int a,b,c,i,j;
45 ArcNode *p,*s;
46 printf("请输入图中顶点的个数：\n");
47 scanf("%d",&Num);
48 Build_VAdjacencyList();
49for(i=0;i<Num;i++)
50 {
51for(j=0;j<Num;j++)
52if(i==j)
53 {
54 map[i][j]=0;
55 map2[i][j]=0;
56 }
57else 58 {
59 map[i][j]=MAX;
60 map2[i][j]=MAX;
61 }
62 }
63 printf("请输入图中边的个数：\n");
64 scanf("%d",&Number);
65 printf("请输入各条边的两个顶点以及边的权值:\n");
66for(i=0;i<Number;i++)
67 {
68 scanf("%d%d%d",&a,&b,&c);
69if(map2[a-1][b-1]>c) ///////建立此图的有向图的邻接矩阵 70 {
71 map2[a-1][b-1]=c;
72 }
73 74 75if(map[a-1][b-1]>c) /////这里的2个if为建立此图的无向图的邻接矩阵 76 map[a-1][b-1]=c;
77if(map[b-1][a-1]>c) ///// 78 map[b-1][a-1]=c;
79 80 81 p=AdjList[a-1].fistarc; /////以下是建立邻接表 82if(p==NULL)
83 {
84 s=(ArcNode *)malloc(sizeof(ArcNode));
85 s->adjvex=b-1;
86 s->weight=c;
87 s->nextarc=NULL;
88 AdjList[a-1].fistarc=s;
89 }
90else 91 {
92while(p->nextarc!=NULL)
93 {
94 p=p->nextarc;
95 }
96 s=(ArcNode *)malloc(sizeof(ArcNode));
97 s->adjvex=b-1;
98 s->weight=c;
99 s->nextarc=NULL;
100 p->nextarc=s;
101 }
102 }
103104}
105void ShowAdjacencyList() ///////以邻接表的形式输出各顶点所连接的点106{
107if(Num==0)
108 printf("请先建立有向图!\n");
109else110 {
111int i;
112 ArcNode *p;
113for(i=0;i<Num;i++)
114 {
115 printf("从%d直接可达的点有:",i+1);
116 p=AdjList[i].fistarc;
117while(p!=NULL)
118 {
119 printf("%d、",p->adjvex+1);
120 p=p->nextarc;
121 }
122 printf("\n");
123 }
124 }
125}
126void ShowAdjacencyListDegree() //////////////////以邻接表的形式输出各顶点的度127{
128if(Num==0)
129 printf("请先建立有向图!\n");
130else131 {
132int i,j,sum;
133 ArcNode *p;
134for(i=0;i<Num;i++)
135 {
136 sum=0;
137 p=AdjList[i].fistarc;
138//出度139while(p!=NULL)
140 {
141 sum++;
142 p=p->nextarc;
143 }
144//入度145for(j=0;j<Num;j++)
146 {
147if(j!=i)
148 {
149 p=AdjList[j].fistarc;
150while(p!=NULL)
151 {
152153if(p->adjvex==i)
154 sum++;
155 p=p->nextarc;
156 }
157 }
158 }
159 printf("顶点%d的度为:%d\n",i,sum);
160 }
161 }
162}
163void TopologicalSortAdjacencyList() ///////邻接表的拓扑排序164{
165if(Num==0)
166 printf("请先建立有向图!\n");
167else168 {
169 memset(topocount,0,sizeof(topocount));
170 memset(topoflag,0,sizeof(topoflag));
171int i,sum,k=0;
172 ArcNode *p;
173 sum=0;
174while(sum<Num)
175 {
176for(i=0;i<Num;i++)
177 {
178if(topoflag[i]==0)
179 {
180 p=AdjList[i].fistarc;
181while(p!=NULL)
182 {
183 topoflag[p->adjvex]=1;
184 p=p->nextarc;
185 }
186 }
187 }
188for(i=0;i<Num;i++)
189 {
190if(topoflag[i]==0)
191 {
192 topoflag[i]=2;
193 topocount[sum]=i+1;
194 sum++;
195break;
196 }
197 }
198if(i==Num+1)
199 {
200 printf("此有向图有环!\n");
201 k=1;
202break;
203 }
204for(i=0;i<Num;i++)
205 {
206if(topoflag[i]==1)
207 topoflag[i]=0;
208 }
209 }
210if(k==0)
211 {
212for(i=0;i<Num;i++)
213 printf("%d ",topocount[i]);
214 printf("\n");
215 }
216 }
217}
218void DFS(ArcNode *s)
219{
220 ArcNode *p;
221while(s!=NULL)
222 {
223if(flag[s->adjvex]==0)
224 s=s->nextarc;
225else226 {
227 flag[s->adjvex]=0;
228 num[K]=s->adjvex;
229 K++;
230 p=AdjList[s->adjvex].fistarc;
231 DFS(p);
232 s=s->nextarc;
233 }
234 }
235}
236void DFSAdjacencyList() ///////////////////对邻接表进行深度优先遍历237{
238if(Num==0)
239 printf("请先建立有向图!\n");
240else241 {
242int i,k;
243 K=0;
244 ArcNode *p;
245for(i=0;i<Num;i++)
246 flag[i]=1;
247for(k=0;k<Num;k++)
248 {
249if(flag[k]==1)
250 {
251 num[K]=k;
252 K++;
253 p=AdjList[k].fistarc;
254 DFS(p);
255 }
256 }
257 printf("深度优先遍历的顺序为:\n");
258for(i=0;i<Num;i++)
259 printf("%d ",num[i]+1);
260 printf("\n");
261 }
262}
263void BFSAdjacencyList() ///////对邻接表进行广度优先遍历264{
265if(Num==0)
266 printf("请先建立有向图!\n");
267else268 {
269int i,j;
270 ArcNode *p;
271 K=0;
272 j=0;
273for(i=0;i<Num;i++)
274 flag[i]=1;
275 memset(count,0,sizeof(count));
276for(i=0;i<Num;i++)
277 {
278if(flag[i]==1)
279 {
280 flag[i]=0;
281 num[K]=i;
282 K++;
283while(j<K)
284 {
285 p=AdjList[num[j]].fistarc;
286 j++;
287while(p!=NULL)
288 {
289if(flag[p->adjvex]==1)
290 {
291 num[K]=p->adjvex;
292 K++;
293 flag[p->adjvex]=0;
294 }
295 p=p->nextarc;
296 }
297 }
298 }
299 }
300 printf("广度优先遍历的顺序为:\n");
301for(i=0;i<Num;i++)
302 printf("%d ",num[i]+1);
303 printf("\n");
304 }
305}
306void AdjacencyListPrim() ///////////////////用Prim算法对邻接矩阵求最小生成树307{
308if(Num==0)
309 printf("请先建立有向图!\n");
310else311 {
312int min1,pi,i,j,ans=0;
313for(i=0;i<Num;i++)
314 {
315 flag[i]=0;
316 count[i]=map[0][i];
317 }
318 flag[0]=1;
319 count[0]=0;
320for(i=1;i<Num;i++)
321 {
322 min1=MAX;
323for(j=0;j<Num;j++)
324 {
325if(flag[j]==0&&count[j]<min1)
326 {
327 min1=count[j];
328 pi=j;
329 }
330 }
331if(min1==MAX)
332 {
333 printf("图不连通!\n");
334return;
335 }
336 flag[pi]=1;
337for(j=0;j<Num;j++)
338 {
339if(flag[j]==0&&count[j]>map[pi][j])
340 count[j]=map[pi][j];
341 }
342 }
343for(i=0;i<Num;i++)
344 {
345 ans+=count[i];
346 }
347 printf("%d\n",ans);
348 }
349}
350void AdjacencyListDijkstra() ////////////对邻接矩阵对各顶点到其他顶点的最短距离，在此用的是Dijkstra 算法351{
352if(Num==0)
353 printf("请先建立有向图!\n");
354else355 {
356int min1,pi,i,j,k;
357for(k=0;k<Num;k++)
358 {
359 memset(flag,0,sizeof(flag));
360 memset(count,0,sizeof(count));
361for(i=0;i<Num;i++)
362 {
363 flag[i]=0;
364 count[i]=map2[k][i];
365 }
366 flag[k]=1;
367 count[k]=0;
368for(i=1;i<Num;i++)
369 {
370 min1=MAX;
371for(j=0;j<Num;j++)
372 {
373if(flag[j]==0&&count[j]<min1)
374 {
375 min1=count[j];
376 pi=j;
377 }
378 }
379 flag[pi]=1;
380for(j=0;j<Num;j++)
381 {
382if(flag[j]==0&&count[j]>count[pi]+map2[pi][j])
383 count[j]=count[pi]+map2[pi][j];
384 }
385 }
386for(i=0;i<Num;i++)
387 {
388 map3[k][i]=count[i];
389 }
390 }
391for(i=0;i<Num;i++)
392 {
393for(j=0;j<Num;j++)
394 {
395if(i==j)
396continue;
397if(map3[i][j]!=MAX)
398 printf("顶点%d与顶点%d之间的最短距离为:%d\n",i+1,j+1,map3[i][j]);
399else400 printf("顶点%d与顶点%d之间的最短距离为:+∞\n",i+1,j+1);
401 }
402403 }
404 }
405}
406void ShowMenu() //////////////////////菜单407{
408 printf("-----------------------------------------------------\n");
409 printf("|对图的操作如下: |\n");
410 printf("-----------------------------------------------------\n");
411 printf("| 1.建立有向图 ; 2.输出该临接表 |\n");
412 printf("| 3.输出个顶点的度 ; 4.进行拓扑排序 |\n");
413 printf("| 5.深度优先遍历 ; 6.广度优先遍历 |\n");
414 printf("| 7.无向图最小生成树 ; 8.有向图求最短路径 |\n");
415 printf("| 0.退出 |\n");
416 printf("-----------------------------------------------------\n");
417 printf("请选择想要进行的操作:\n");
418 scanf("%d",&choose);
419420}
421int main() ///////////////////////////////////主函数422{
423 Num=0;
424 Number=0;
425 ShowMenu();
426while(1)
427 {
428if(choose==0)
429break;
430elseif(choose==1)
431 {
432 BuildAdjacencyList();
433 ShowMenu();
434 }
435elseif(choose==2)
436 {
437 ShowAdjacencyList();
438 ShowMenu();
439 }
440elseif(choose==3)
441 {
442 ShowAdjacencyListDegree();
443 ShowMenu();
444 }
445elseif(choose==4)
446 {
447 TopologicalSortAdjacencyList();
448 ShowMenu();
449 }
450elseif(choose==5)
451 {
452 DFSAdjacencyList();
453 ShowMenu();
454 }
455elseif(choose==6)
456 {
457 BFSAdjacencyList();
458 ShowMenu();
459 }
460elseif(choose==7)
461 {
462 AdjacencyListPrim();
463 ShowMenu();
464 }
465elseif(choose==8)
466 {
467 AdjacencyListDijkstra();
468 ShowMenu();
469 }
470471 }
472return0;
473 }
原文：http://www.cnblogs.com/wujiyang/p/4491858.html
内容总结
以上是互联网集市为您收集整理的图的基本算法全部内容，希望文章能够帮你解决图的基本算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】