图的最短路径.docx

《图的最短路径.docx》由会员分享，可在线阅读，更多相关《图的最短路径.docx（16页珍藏版）》请在三一办公上搜索。

1、图的最短路径图的最短路径 一、问题描述 最小生成树是一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有个结点，并且有保持图连通的最小的边，最小生成树在实际问题中具有一定的应用价值，如在城市之间建设网络，要保证网络的连通性，求最经济的设计方法。求解最小生成树时，可以采用普里母算法和克鲁斯卡尔算法。 二、基本要求 1、 选择合适的储存结构，完成网的建立； 2、 利用普里母算法求网的最少生成树，并输出结果； 3、 利用克鲁斯卡尔求网的最少生成树，并输出结果； 4、 采用邻接矩阵和邻接表两种储存结构； 三、测试数据 对右图进行测试 右图是6个顶点的10个边的连通图 六个顶点分别是

2、v1 v2 v3 v4 v5 v6 边和边上的权植分别是 v1 v2 6 v1 v3 1 v1 v4 5 v2 v3 5 v2 v5 3 v3 v4 5 v3 v5 6 v3 v6 4 v4 v6 2 v5 v6 6 wilyes11收集 博客(与学习无关)： 四、算法思想 克鲁斯卡尔算法思想是：假设连通图N=，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。 普里母算法思想是：假

3、设N=是连通图，是上最小生成树中边的集合。算法从u0，TE= 开始，重复执行下述操作：在所有uU，vVU的边E中找一条代价最小的边并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有条边，则为的最小生成树。为实现这个算法需附设辅助数组closedge,以记录从U到V-U具有最小代价的边。对每个顶点viV-U，在辅助数组中存在一个相应分量closedgei-1，它包括两个域，其中lowcost储存该边的权。显然，closedgei-1.lowcost=Mincost(u,vi)|uU,vexU, vex 域存储该边依附的在U中的顶点 。 五、模块 克鲁斯卡尔算法和普里母算法都要用到以下的

4、算法 int LocateVex(Mgraph G,Vertex u)，矩阵求点u所在位置； void CreateGraph(Mgraph/ ALGraph &G)，建立带权邻接矩阵/邻接表的结构； void kruskal2(ALGraph G)，邻接链表的克鲁斯卡尔算法； void kruskal(MGraph G)，邻接矩阵的克鲁斯卡尔算法； int minimum(ALGraph/ MGraph G,struct arry wq)，邻接表/邻接矩阵求最小的权值； void MiniSpanTree_PRIM1(ALGraph G,VertexType u)，邻接表的普里姆算法； vo

5、id MiniSpanTree_PRIM2(MGraph G,VertexType u)，邻接矩阵的普里姆算法。 六、数据结构/(ADT) 1、邻接表的储存结构如下 邻接表的结点结构信息 typedef struct ArcNode/*定义边结点*/ int adjvex;/*该弧指向的顶点的位置*/ int weight;/*该弧的权重*/ struct ArcNode *nextarc;/*指向下一条弧的指针*/ ArcNode; 邻接表的表头向量的结点结构信息 typedef struct VNode VertexType data; /*顶点信息*/ wilyes11收集 博客(与学习

6、无关)： ArcNode *firstarc;/*指向第一条依附该顶点的弧的指针*/ VNode,AdjListMAX_VERTEX_NUM;/定义图结点 邻接表的表头带权图的结构信息 typedef struct AdjList vertices;/*表头向量*/ int vexnum,arcnum;/顶点数和弧数 ALGraph;/定义图 2、邻接矩阵的储存结构如下 typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/*邻接距阵*/ 邻接矩阵带权图的结构信息 struct MGraph Vertex vexsMAX_VERTEX_NUM;/

7、*顶点向量*/ AdjMatrix arcs;/*邻接矩阵*/ int vexnum,arcnum;/*顶点数和弧数*/ ; 七、源程序 #include #include #include #define MAX_NAME 5 /*顶点值最大字符数*/ #define MAX_VERTEX_NUM 20 /*最大顶点数*/ typedef char VertexMAX_NAME;/*(邻接矩阵用)顶点名字串*/ typedef char VertexTypeMAX_NAME;/*(邻接链表用)顶点名字串*/ typedef int AdjMatrixMAX_VERTEX_NUMMAX_VER

8、TEX_NUM;/*邻接距阵*/ /*链表的结点结构信息*/ typedef struct ArcNode/*定义边结点*/ int adjvex;/*该弧指向的顶点的位置*/ int weight;/*该弧的权重*/ struct ArcNode *nextarc;/*指向下一条弧的指针*/ ArcNode; /*表头向量的结点结构信息*/ typedef struct VNode VertexType data;/*顶点信息*/ ArcNode *firstarc;/*指向第一条依附该顶点的弧的指针*/ VNode,AdjListMAX_VERTEX_NUM;/定义图结点 wilyes11

9、收集 博客(与学习无关)： /*链表带权图的结构信息*/ typedef struct AdjList vertices;/*表头向量*/ int vexnum,arcnum;/顶点数和弧数 ALGraph;/定义图 /*矩阵带权图的结构信息*/ struct MGraph Vertex vexsMAX_VERTEX_NUM;/*顶点向量*/ AdjMatrix arcs;/*邻接距阵*/ int vexnum,arcnum;/*顶点数和弧数*/ ; struct arry VertexType adjvex; int lowcost; closedgeMAX_VERTEX_NUM; int

10、LocateVex(MGraph G,Vertex u)/矩阵求点u所在位置 int i; for(i=0;iG.vexnum;+i) if(strcmp(u,G.vexsi)=0) return i; return -1; int LocateVe(ALGraph G,VertexType u)/链表求出点u所在位置 int i; /*=*/ /*=邻接矩阵的克鲁斯卡尔算法=*/ /*=*/ void CreateGraph(MGraph &G)/建立带权邻接矩阵结构 int i,j,k,w; Vertex va,vb; for(i=0;iG.vexnum;+i) if(strcmp(G.v

11、erticesi.data,u) = 0) return i; return -1; wilyes11收集 博客(与学习无关)： printf(请输入无向网G的顶点数和边数(分别以空格为分隔):n); scanf(%d %d,&G.vexnum,&G.arcnum); printf(请输入%d个顶点的值:n,G.vexnum,MAX_NAME); for(i=0;iG.vexnum;+i) /* 读入顶点信息*/ scanf(%s,G.vexsi); for(i=0;iG.vexnum;+i)/*初始化邻接矩阵*/ for(j=0;jG.vexnum;+j) G.arcsij=0x7fffff

12、ff; printf(请输入%d条边各自的起点,终点,权值(分别用空格分隔):n,G.arcnum); for(k=0;kG.arcnum;+k)/*读入边*/ scanf(%s%s%d,va,vb,&w); i=LocateVex(G,va); j=LocateVex(G,vb); G.arcsij=G.arcsji=w;/*对称*/ /*邻接矩阵的克鲁斯卡尔算法*/ void kruskal(MGraph G) int setMAX_VERTEX_NUM,i,j;/*set数组用来判断两个点是否在同一个集合里*/ int k=0,a=0,b=0,min=G.arcsab; for(i=0;

13、iG.vexnum;i+) seti=i; printf(最小代价生成树的各条边为:n); while(kG.vexnum-1) for(i=0;iG.vexnum;+i) for(j=i+1;jG.vexnum;+j) if(G.arcsijmin)/*求最小权值的边*/ min=G.arcsij; a=i; b=j; min=G.arcsab=0x7fffffff;/将最小权值改成最大值 if(seta!=setb)/*若a、b两个点不在同一集合里，则输出a、b之间的边*/ /*int s1=setb;*/ wilyes11收集 博客(与学习无关)： printf(%s-%sn,G.vex

14、sa,G.vexsb); k+; for(i=0;iG.vexnum;i+)/将a、b放在同一集合里 if(seti=setb/*s1*/) seti=seta; /*邻接矩阵的克鲁斯卡尔算法*/ void k1 MGraph g; CreateGraph(g); kruskal(g); /*=*/ /*=邻接链表的克鲁斯卡尔算法=*/ /*=*/ void CreateGraph(ALGraph &G) /邻接链表创建带权图 int i,j,k,w; VertexType va,vb; printf(请输入顶点数,边数(请用空格分开):n); /*输入顶点数、弧数*/ scanf(%d %d

15、,&G.vexnum,&G.arcnum); printf(请输入各顶点的值:n); for(i = 0; i G.vexnum; +i)/*初始化顶点值*/ scanf(%s,G.verticesi.data); for(i = 0; i G.vexnum; +i)/初始化vertices数组 G.verticesi.firstarc=NULL; printf(请输入各边的起点,终点,权值(分别用空格分开):n); for(k = 0; k adjvex = j;/初始化 p-weight = w; wilyes11收集 博客(与学习无关)： p-nextarc = G.verticesi.

16、firstarc;/插表头 G.verticesi.firstarc =p; ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode); q-adjvex = i; q-weight = w; q-nextarc = G.verticesj.firstarc; G.verticesj.firstarc = q; /*邻接链表的克鲁斯卡尔算法*/ void kruskal2(ALGraph G) int i,j,min = 0x7fffffff,k = 0;/min用于记录最小权值 int setMAX_VERTEX_NUM;/用于判断两个点是否在同一集合里

17、ArcNode *p,*q,*s; for(i = 0; i G.vexnum; +i) seti = i;/初始化，将每个点自身作为一个集合 while(k G.vexnum - 1) for(i = 0; i nextarc)/查找最小权值的边 if(G.verticesj.firstarc = q) G.verticesj.firstarc = q-nextarc; if(p-weight weight; q = p; j = i; /if-else用于删除最小权值的边 else if(setj!=setq-adjvex)/判断两点是否在同一集合,若不在，则输出这条边for(p = G.

18、verticesj.firstarc; p != q; p = p-nextarc) s = p; s-nextarc = q-nextarc; printf(%s,%s) %dn,G.verticesj.data,G.verticesq-adjvex.data,q-weight); k+; wilyes11收集 博客(与学习无关)： /*int s2=setj;*/ for(i=0;iadjvex; min = 0x7fffffff; /将min置为最大值 void k2 ALGraph G; CreateGraph(G); kruskal2(G); /*=*/ /*=邻接矩阵的普里姆算法=

19、*/ /*=*/ int minimum2(MGraph G,struct arry wq) int i,j; for(i=0;iG.vexnum;i+) if(wqi.lowcost!=0&wqi.lowcost!=0x7fffffff) break; j=i; for(i=0;iwqi.lowcost&wqi.lowcost!=0) j=i; return j; void MiniSpanTree_PRIM2(MGraph G, VertexType u) int i,j,k; k = LocateVex (G,u); for ( j=0; jG.vexnum; +j ) if (j!=k

20、) strcpy(closedgej.adjvex,u); closedgej.lowcost=G.arcskj; closedgek.lowcost = 0; wilyes11收集 博客(与学习无关)： for (i=1; iG.vexnum; +i) k = minimum2(G,closedge); closedgek.lowcost = 0; printf(%s%s ,closedgek.adjvex,G.vexsk); for (j=0; jG.vexnum; +j) if (G.arcskj closedgej.lowcost&closedgej.lowcost!=0) strcp

21、y(closedgej.adjvex,G.vexsk); closedgej.lowcost=G.arcskj; void k3 MGraph g; CreateGraph(g); MiniSpanTree_PRIM2(g,v1); /*=*/ /*=邻接表的普里姆算法=*/ /*=*/ int minimum1(ALGraph G,struct arry wq) int i,j; for(i=0;iG.vexnum;i+) if(wqi.lowcost!=0&wqi.lowcost!=0x7fffffff) break; j=i; for(i=0;iwqi.lowcost&wqi.lowco

22、st!=0) j=i; return j; void MiniSpanTree_PRIM1(ALGraph G, VertexType u) int i,j,k;ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode); k=LocateVe(G,u); for ( j=0; jG.vexnum; +j ) wilyes11收集 博客(与学习无关)： closedgej.lowcost=0x7fffffff; for (j=0;jnextarc) closedgep-adjvex.lowcost=p-weight; strcpy(closedgep-adjv

23、ex.adjvex,u); /for break; /if /for closedgek.lowcost=0; for (i=1; iG.vexnum; +i) k = minimum1(G,closedge); closedgek.lowcost=0; printf(%s%s ,closedgek.adjvex,G.verticesk.data); for (j=0; jnextarc) if(p-weightadjvex=j) closedgej.lowcost=p-weight; strcpy(closedgej.adjvex,G.verticesk.data); void k4 ALG

24、raph G; CreateGraph(G); MiniSpanTree_PRIM1(G,v1); int main int cord; do printf(n=); printf(n 主菜单 ); printf(n 1.邻接矩阵实现克鲁斯算法 ); printf(n 2.邻接链表实现克鲁斯算法 ); printf(n 3.邻接矩阵实现普里姆算法 ); printf(n 4.邻接链表实现普里姆算法 ); wilyes11收集 博客(与学习无关)： printf(n 5.退出程序 ); printf(n=); printf(n 请输入您的选择(1,2,3,4,5) cord=); scanf(%

25、d,&cord); switch(cord) case 1:k1;break; case 2:k2;break; case 3:k3;break; case 4:k4;break; case 5:exit(0); while(cord=5); system(pause); 八、测试情况 程序的测试结果如下： 邻接矩阵实现克鲁斯卡尔运行结果如下 邻接链表实现克鲁斯卡尔如下 wilyes11收集 博客(与学习无关)： 邻接矩阵实现普利姆算法如下 wilyes11收集 博客(与学习无关)： 邻接链表实现普利姆算法如下 人工验证，都正确 九、参考文献 1、严蔚敏，数据结构 C语言，清华大学出版社。 2

26、、谭浩强，c语言程序设计，清华大学出版社。 wilyes11收集 博客(与学习无关)： 小结 通过本次课程设计，我学到了很多。要写好一个程序必须弄清他的最基本的思路，除此之外要有算法思路，会写一些基本函数，程序不是一个非要一个主要的函数或者程序要写完，最好有几个函数组成，以便于利用。编程不像做其它事，它要求编程人员有非常缜密的思维，很好的整体把握能力和很好的调试程序的能力等。决定程序成功与否的往往既是有程序的整体思路和整体算法，也要特别注重细节，一个程序没有整体思路和整体算法是写不出来的，但是细节错误往往也是程序成功的观念，小细节的错误导致运行不成功，结果错误，感觉所有的功夫都白费了，我在此次

27、课程设计中深有体会。编程不是轻而易举的，必须要考虑什么储存结构更适合那个算法，本次就用邻接矩阵和邻接表，而没用十字链表，十字链表不合适，而且它的操作相对比较复杂，在小程序中没有优势，还有，算法的实现须要哪些变量，变量中信息又需要哪些，中间算法的需要又用到哪些中间变量，这些没有一定的编程语言的基础和编程经验是无法完成的 在写程序的过程中我深刻体会到：如果要写程序，一定要有一定的语言基础知识，此外还要有形成的算法思想及一些基本的储存结构都要会写。没有一点点的语言基础理所当然是写不出来的，所以写程序时感觉到当时应该更努力的学习，深刻的体会到“书到用时方恨少”。邻接表和邻接矩阵的储存结构书上给了一个大

28、概的结构，但是要根据需要辨别储存结构中哪些变量要用，哪些不要用，根据需要来取舍，还有一些变量的在不同的地方用不同的用处，要根据所写程序的需要来辨别他的用处不同即它要保存什么变量。当然此次程序设计中普利姆算法书上有一个大致的结构，所以我是根据书上的程序写的，但是中间有好多的函数要自己独立完成，例如求最小权值minimum函数，在写此函数时我多次出错，最后还是在同学的帮助下完成。 此次我领略到以前学习的知识的重要性和分工合作精神的重要性，集体编程和个人编程有很大不同，相互间独立而又紧密联系在一起，如创建带权的邻接矩阵和邻接表时，我是参考以前程序编写的，但是我要知道相应的的算法中需要哪些变量和函数，

29、进而完成编写。还有编程要实用，求最小生成树是为了求图的最短路径，如我编写的两个算法中，带权的图的邻接矩阵和邻接表中的边，我不仅仅要添加边，还要考虑到边的权值，以求最短的路径。 在本次课程设计中，虽然以前我对两种算法只有一个大概的整体思路，但是没有一个具体详细的思路，尤其是中间的许多函数不是很了解，但在我不断的查看书籍和多次虚心求教下我还是顺利地完成了。求最短路径问题看似是一个很简单的问题，但在实际的程序编写时如果没有学好C语言和数据结构知识是很难完成。例如，算法思想是解决本问题的根本关键，数据结构课本175页有它的介绍。 从这次课程设计中，我了解到知识的重要性，不论是书本的，还是人际交往上的，让我感受颇深！ wilyes11收集 博客(与学习无关)：