《数据结构——C语言描述第5章-图.pptx》由会员分享，可在线阅读，更多相关《数据结构——C语言描述第5章-图.pptx（161页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构C语言描述（慕课版）第5章图编著：张同珍&学校：上海交通大学图1.图的基本概念、术语3.图的遍历和连通性4.最小生成树2.图的存储5.最短路径6.AOV网和AOE网图在图中，元素结点用顶点来表示，元素间的关系用顶点间的边来表示，图中任意两个元素之间都可能有相互制约关系。图可以用一个二元组G=(V,E)表示，其中V是顶点(即元素)的非空集合，E是两个顶点间边（弧）的集合。有向边：带有方向性，用带尖括号的顶点对。如图G1中的。有向图：由顶点集和有向边集合组成的图，这里图G1就是一个有向图。无向边：边无方向性，用带园括号的顶点对表示。如(C,A)表示C和A之间有条无向边。无向图：由顶点集和无
2、向边集合构成的图称为无向图，如图G2就是一个无向图。顶点间有边相连，如(vi,vj)是一条无向边，则称vi和vj邻接。顶点间有邻接关系：有向图中，该顶点射出的有向边的条数。顶点的出度：有向图中，射入该顶点的有向边的条数。图G1中顶点A的入度为3、出度为1。顶点的入度：无向图中，和该顶点相邻的边的条数。G2中，顶点B的度为1、顶点A的度为3。顶点的度：无向完全图：有向完全图：边带有权重的有向图，也称网络。加权有向图：边带有权重的无向图，也称网络。G3、G4分别是一个加权无向图和加权有向图。加权无向图：01030204顶点i到顶点j之间的路径：从顶点i出发经过若干条无向边或者有向边到达顶点j。路径
3、的长度：顶点i到顶点j之间的无向边或有向边的条数，如果边上有权重，路径长度也可以用路径上所有边的权重之和。图G2中，顶点序列C,A,D,B表示一条由无向边(C,A),(A,D),(D,B)构成的长度为3的路径。图G4中，顶点序列A,D,C,E表示一条由有向边,构成的长度为7的路径。路径上除了第一个顶点和最后一个顶点可能相同之外，其余各顶点都不相同。简单路径：简单路径上如果第一个顶点和最后一个顶点相同。简单回路或简单环：在图G3中顶点序列A,D,E,F是简单路径；顶点序列A,D,E,F,B,A是简单路径，也是简单回路；顶点序列A,D,C,E,D,B不是简单路径；顶点序列A,D,C,E,D,B,A
4、是回路，但不是简单回路。010304子图：两个图G=(V,E)，G=(V,E)，且V是V的子集，E是E的子集，则称G是G的子图，如图所示，图T1、T2、T3都是图T的子图。顶点i、j 之间是连通的：如果顶点i和j之间有路径存在。连通图：在一个无向图中，如果任意两个顶点对之间都是连通的，称该无向图G是连通图。连通分量：无向图的极大连通子图。02强连通分量：强连通图：在一个有向图G中，如果任意两个顶点对之间都是连通的，称有向图G是强连通图。有向图的极大连通子图。有向图G1是强连通图，无向图G2是连通图。无向图G5和它的三个连通分量。有向图G6和它的三个强连通分量。（a）有向图G6（b）G6的三强连
5、通分量连通图的生成树：它的极小连通子图。该连通子图包含连通图的所有n个顶点，但只含它的n-1条边。如果去掉一条边，这个子图将不连通。如果增加一条新的边(vi,vj)，则因顶点vi和vj之间原本连通，加上新加的这条边便形成了回路。01OPTION02OPTION03OPTION右图G7和它的两个不同的生成树：图1.图的基本概念、术语3.图的遍历和连通性4.最小生成树2.图的存储5.最短路径6.AOV网和AOE网图的存储邻接矩阵存储邻接表存储多重邻接表和十字链表图的邻接矩阵存储0102顶点V用一个一维数组来存储；边用一个二维数组即一个n行n列的矩阵A来存储（n为顶点的个数），无边用0表示、有边用1
6、表示。对有向图或无向图G=(V,E)：一维顶点数组中顶点的存储没有固定的顺序，可随机存储；二维边矩阵中，含义和顶点在一维数组中的下标相关；容易计算顶点的入度、出度、度；边矩阵中主对角线全为0；无向图的边矩阵中，一条边存储了2次，是关于主对角线对称的；存储可以仅存上三角或者下三角。用邻接矩阵存储特点：用加权邻接矩阵表示加权有向图或无向图：010203对角线元素为0顶点间有边相连，用边的权重表示顶点间无边相连，用无穷大表示（在内存中表示为一个很大的整数。邻接矩阵存储特点：存顶点信息的一维数组空间消耗n；存边信息的二维数组空间消耗n2；对有向图即便计算边的条数也要n2时间。故邻接矩阵最适合边比较多的
7、情况，即稠密图。邻接矩阵存储实现：#defineDefaultNumVertex20#defineMAXNUM9999typedefcharverType;typedefintedgeType;typedefstructintverts,edges;/图的实际顶点数和实际边数intmaxVertex;/图顶点的最大可能数量verType*verList;/保存顶点数据的一维数组edgeType*edgeMatrix;/保存邻接矩阵内容的二维数组edgeTypenoEdge;/无边的标志，一般图为0，网为无穷大MAXNUMintdirected;/有向图为1，无向图为0Graph;邻接矩阵存储实
8、现：/初始化图结构g，direct为是否有向图标志，e为无边数据voidinitialize(Graph*g,intdirect,edgeTypee);/返回图当前顶点数intnumberOfVertex(Graph*g)returng-verts;/返回图当前边数intnumberOfEdge(Graph*g)returng-edges;/返回顶点为vertex值的元素在顶点表中的下标intgetVertex(Graph*g,verTypevertex);/判断某两个顶点间是否有边intexistEdge(Graph*g,verTypevertex1,verTypevertex2);/返回顶
9、点vertex的第一个邻接点,如果无邻接点返回-1intgetFirstNeighbor(Graph*g,verTypevertex);邻接矩阵存储实现：/返回顶点vertex1的相对vertex2的下一个邻接点，如果无下一个邻接点返回-1intgetNextNeighbor(Graph*g,verTypevertex1,verTypevertex2);/显示邻接矩阵的值voiddisp(Graph*g);/插入顶点voidinsertVertex(Graph*g,verTypevertex);/插入边voidinsertEdge(Graph*g,verTypevertex1,verTypev
10、ertex2,edgeTypeedge);/删除顶点voidremoveVertex(Graph*g,verTypevertex);/删除边voidremoveEdge(Graph*g,verTypevertex1,verTypevertex2);/返回顶点vertex的第一个邻接点,如果无邻接点返回-1邻接矩阵存储实现：/-函数实现-/初始化图结构g，direct为是否有向图标志，e为无边数据voidinitialize(Graph*g,intdirect,edgeTypee)inti,j;/初始化属性g-directed=direct;g-noEdge=e;g-verts=0;g-edge
11、s=0;g-maxVertex=DefaultNumVertex;邻接矩阵存储实现：/为存顶点的一维数组和存边的二维数组创建空间g-verList=(verType*)malloc(sizeof(verType)*g-maxVertex);g-edgeMatrix=(edgeType*)malloc(sizeof(edgeType*)*g-maxVertex);for(i=0;imaxVertex;i+)g-edgeMatrixi=(edgeType*)malloc(sizeof(edgeType)*g-maxVertex);/初始化二维数组，边的个数为0for(i=0;imaxVertex;
12、i+)for(j=0;jmaxVertex;j+)if(i=j)g-edgeMatrixij=0;/对角线元素elseg-edgeMatrixij=g-noEdge;邻接矩阵存储实现：/判断某两个顶点是否有边intexistEdge(Graph*g,verTypevertex1,verTypevertex2)inti,j;/找到vertex1和vertex2的下标for(i=0;iverts;i+)if(g-verListi=vertex1)break;for(j=0;jverts;j+)if(g-verListj=vertex2)break;if(g-edgeMatrixij=g-noEdg
13、e)return0;elsereturn1;voidinsertEdge(Graph*g,verTypevertex1,verTypevertex2,edgeTypeedge)/插入边inti,j;/找到vertex1和vertex2的下标for(i=0;iverts;i+)if(g-verListi=vertex1)break;for(j=0;jverts;j+)if(g-verListj=vertex2)break;if(i=g-verts)|(j=g-verts)exit(1);g-edgeMatrixij=edge;g-edges+;if(g-directed=0)/如果是无向图，矩阵
14、中关于主对角线的对称点也要设置g-edgeMatrixji=edge;/删除顶点voidremoveVertex(Graph*g,verTypevertex)inti,j,k,count;/找到该顶点在顶点表中的下标for(i=0;iverts;i+)if(g-verListi=vertex)break;if(i=g-verts)exit(1);/该顶点不在顶点表中/计数被删除顶点射出的边的条数for(j=0;jverts;j+)if(g-edgeMatrixij!=g-noEdge)count+;if(g-directed=1)/有向图还需计数被删除顶点射出的边的条数for(j=0;jver
15、ts;j+)if(g-edgeMatrixji!=g-noEdge)count+;/删除邻接矩阵的第i行和第i列/将所有行号大于i的行上移一行for(j=i;jverts-1;j+)for(k=0;kverts;k+)g-edgeMatrixjk=g-edgeMatrixj+1k;/将所有列号大于i的列左移一列for(j=i;jverts-1;j+)for(k=0;kverts;k+)g-edgeMatrixjk=g-edgeMatrixj+1k/图中边数减去删除的边数g-edges=g-edges-count;/顶点表中删除第i顶点for(j=i;jverts-1;j+)g-verListj
16、=g-verListj+1;/顶点数减1g-verts-;邻接矩阵存储实现：/返回顶点vertex的第一个邻接点，如果无邻接点返回-1intgetFirstNeighbor(Graph*g,verTypevertex)inti,j;for(i=0;iverts;i+)if(g-verListi=vertex)break;if(i=g-verts)exit(1);for(j=0;jverts;i+)if(g-edgeMatrixij!=g-noEdge)break;if(j=g-verts)return-1;returnj;邻接矩阵存储实现：voiddisp(Graph*g)/显示邻接矩阵的值i
17、nti,j;for(i=0;iverts;i+)for(j=0;jverts;j+)printf(%d,g-edgeMatrixij);printf(n);邻接矩阵实现的简单测试：voidmain()Graphg;inti;verTypev1,v2;edgeTypevalue;initialize(&g,1,0);for(i=0;i4;i+)/插入4个顶点insertVertex(&g,A+i);for(i=0;iverts;/返回图当前边数intnumberOfEdge(Graph*g)returng-edges;/返回顶点为vertex值的元素在顶点表中的下标intgetVertex(Gr
18、aph*g,verTypevertex);/判断某两个顶点是否有边intexistEdge(Graph*g,verTypevertex1,verTypevertex2);/返回顶点vertex的第一个邻接点,如果无邻接点返回-1intgetFirstNeighbor(Graph*g,verTypevertex);邻接表实现：/返回顶点vertex1的相对vertex2的下一个邻接点,/如果无下一个邻接点返回-1intgetNextNeighbor(Graph*g,verTypevertex1,verTypevertex2);/显示邻接表的值voiddisp(Graph*g);/插入顶点void
19、insertVertex(Graph*g,verTypevertex);/插入边voidinsertEdge(Graph*g,verTypevertex1,verTypevertex2,edgeTypeedge);/删除顶点voidremoveVertex(Graph*g,verTypevertex);/删除边voidremoveEdge(Graph*g,verTypevertex1,verTypevertex2);邻接表实现：/-函数实现-/初始化图结构g,direct为是否有向图标志，e为无边数据voidintialize(Graph*g,intdirect)/属性初始化g-directe
20、d=direct;g-verts=0;g-edges=0;g-maxVertex=DefaultNumVertex;g-verList=(verNode*)malloc(sizeof(verNode)*g-maxVertex);邻接表实现：intgetVertex(Graph*g,verTypevertex)/返回顶点为vertex值的元素在顶点表中的下标inti;for(i=0;iverts;i+)if(g-verListi.data=vertex)break;if(i=g-verts)exit(1);returni;/判断某两个顶点是否有边intexistEdge(Graph*g,verT
21、ypevertex1,verTypevertex2)inti,j;edgeNode*p;邻接表实现：/求顶点值为vertex1和vertex2的下标i、jfor(i=0;iverts;i+)if(g-verListi.data=vertex1)break;for(j=0;jverts;j+)if(g-verListj.data=vertex2)break;p=g-verListi.link;while(p)if(p-ver=j)break;if(p)return1;elsereturn0;邻接表实现：voidinsertVertex(Graph*g,verTypevertex)/插入顶点if(
22、g-verts=g-maxVertex)exit(1);g-verts+;g-verListg-verts-1.data=vertex;g-verListg-verts-1.link=NULL;voidinsertEdge(Graph*g,verTypevertex1,verTypevertex2,edgeTypeedge)/插入边inti,j;edgeNode*p;邻接表实现：/求顶点值为vertex1和vertex2的下标i、jfor(i=0;iverts;i+)if(g-verListi.data=vertex1)break;for(j=0;jverts;j+)if(g-verListj
23、.data=vertex2)break;if(i=g-verts)|(j=g-verts)exit(1);/创建边结点并设置边结点中的值p=(edgeNode*)malloc(sizeof(edgeNode);p-ver=j;p-edge=edge;p-next=g-verListi.link;邻接表实现：g-verListi.link=p;g-edges+;if(g-directed=0)/如果是无向图，矩阵中关于主对角线的对称点也要设置p=(edgeNode*)malloc(sizeof(edgeNode);p-ver=i;p-edge=edge;p-next=g-verListj.lin
24、k;g-verListj.link=p;/注意不需要edges+;邻接表实现：voidremoveVertex(Graph*g,verTypevertex)/删除顶点inti,j;intcnt;edgeNode*p,*q;/找到该顶点在顶点表中的下标for(i=0;iverts;i+)if(g-verListi.data=vertex)break;if(i=g-verts)exit(1);/该顶点不在顶点表中/删除所有由顶点i射出的边p=g-verListi.link;cnt=0;/被删除的边结点的个数邻接表实现：while(p)g-verListi.link=p-next;free(p);c
25、nt+;p=g-verListi.link;/在所有的边表中删除所有射入顶点i的边，同样适应无向图for(i=0;iverts;i+)p=g-verListi.link;q=NULL;while(p)if(p-ver=i)break;q=p;邻接表实现：p=p-next;if(!p)continue;if(!q)/边结点的首结点ver为ig-verListi.link=p-next;free(p);cnt+;continue;q-next=p-next;free(p);cnt+;邻接表实现：/在顶点表中删除顶点for(j=i;jverts-1;j+)g-verListj.data=g-verL
26、istj+1.data;g-verListj.link=g-verListj+1.link;/将所有边表中ver值大于i的全部减1for(j=0;jverts;j+)p=g-verListj.link;while(p)if(p-veri)p-ver-;p=p-next;g-verts-;if(!directed)cnt=cnt/2;g-edges=g-edges-cnt;图的存储邻接矩阵存储邻接表存储多重邻接表和十字链表无向图每条边都用了两个边结点，如边(A,C)既在顶点A的边表中有一个边结点也在顶点C的边表中有一个边结点，同一条边被存储了两次。多重邻接表：多重邻接表中每个边仅使用一个结点来表
27、示，即只存储一遍，但这个边结点同时在该边邻接的两个顶点的边表中被链。用邻接表表示有向图时，可以很方便地得出某顶点所有射出的边；而用逆邻接表表示有向图时，可以很方便地得出某顶点所有射入的边。多重邻接表中每个边仅使用一个结点来表示，即只存储一遍，但这个边结点同时在该边邻接的两个顶点的边表中被链。十字链表：现在将邻接表和逆邻接表结合在一起。图1.图的基本概念、术语3.图的遍历和连通性4.最小生成树2.图的存储5.最短路径6.AOV网和AOE网图的遍历深度优先遍历广度优先遍历深度优先遍历DFS0102选中第一个未访问的顶点作为起始顶点。访问该顶点并对该顶点加已访问过的标志。深度优先遍历DFS访问方式类
28、似于树的前序访问。它的访问方式如下：04如果还有顶点未被访问，则选中其中一个作为起始顶点，转向2。如果所有的顶点都被访问到，则结束。03依次从顶点的未被访问过的第一个、第二个、第三个邻接顶点出发，转向2，再进行深度优先搜索。显然深度优先遍历的结果不唯一。图的DFS遍历非递归算法思路：不同之处在于图中有回路，某个顶点在一条路径上被访问后可能通过另外一条路径再次到达。为了避免顶点的重复访问，遍历时需要对访问过的顶点加标记，加了访问标记的顶点不再被二次访问。深度优先遍历DFS的实现方法和树的前序算法类似。深度优先遍历DFS的实现：voidDFS_Traveling(Graph*g,verTypest
29、art)stacks;edgeNode*p;inti,j;intverCnt;/记录已经访问的顶点个数/置顶点读取标志为未读0，并找到start顶点的下标j=-1;for(i=0;iverts;i+)g-verListi.flag=0;if(g-verListi.data=start)j=i;verCnt=0;if(j=-1)exit(1);/start顶点不存在/从start结点开始访问initialize(&s);printf(%c,g-verListj.data);/访问顶点g-verListj.flag=1;/给顶点置访问过的标志1verCnt+;while(verCntverts)/
30、外循环p=g-verListj.link;while(!p|g-verListp-ver.flag=1)/在顶点表中另找一个未被访问过的顶点/作为起始顶点开始DFS访问j=(j+1)%g-verts;p=g-verListj.link;push(&s,p);while(!isEmpty(&s)/内循环p=top(&s);pop(&s);if(p-next)push(&s,p-next);/边表中下条边进栈if(g-verListp-ver.flag=0)printf(%c,g-verListp-ver.data);/访问顶点g-verListp-ver.flag=1;/给顶点置访问过的标志1v
31、erCnt+;if(verCnt=g-verts)break;if(g-verListp-ver.link)push(&s,g-verListp-ver.link);j=(j+1)%g-verts;/在顶点表中循环一次程序执行过程中对所有顶点和边都访问了一遍，因此它的时间代价和顶点数n及边数e都相关，时间复杂度为O(n+e)。图的遍历深度优先遍历广度优先遍历广度优先遍历BFS0102选中第一个未访问的顶点作为起始顶点。访问该顶点并对该顶点加已访问过的标志。广度优先遍历类似于树结构从树根出发的层次遍历。它的访问方式如下：04依次对顶点W1、W2、W3Wm转向操作3。03依次访问顶点的未被访问过的
32、第一个、第二个、第三个第m个邻接顶点W1、W2、W3Wm，进行访问且进行标记。05如果还有顶点未被访问，则在其中选中一个作为起始顶点，转向2。如果所有的顶点都被访问到，则结束。显然广度优先遍历的结果也不唯一。图的BFS遍历非递归算法思路：和树的层次遍历方法类似，顶点访问之后进队，如果队不空，进入循环。此时判断是否图中顶点全部访问过，如果还有未被访问过的顶点，任取其中之一作为新的起始顶点继续进行广度优先遍历，直至无向图中的所有顶点都被访问过。循环体为：队首顶点出队，对它的所有未被访问过的邻接顶点进行访问并依次进队，进入下一轮循环，如此反复直到队空。广度优先遍历DFS的实现：voidBFS_Tra
33、veling(Graph*g,verTypestart)/广度优先遍历Queueq;edgeNode*p;inti,j,k,t;intverCnt;/记录已经访问的顶点个数/置顶点的访问标志为0,且找到start结点的下标initialize(&q,g-verts);j=-1;for(i=0;iverts;i+)g-verListi.flag=0;if(g-verListi.data=start)j=i;verCnt=0;if(j=-1)exit(1);/start顶点不存在/从start结点开始访问printf(%c,g-verListj.data);/访问顶点g-verListj.flag
34、=1;/给顶点置访问过的标志1verCnt+;while(verCntverts)/外循环enQueue(&q,j);while(!isEmpty(&q)/内循环k=front(&q);deQueue(&q);p=g-verListk.link;/从顶点k的顶点表中的首结点开始看while(p&verCntverts)t=p-ver;if(g-verListt.flag=0)printf(%c,g-verListt.data);/访问顶点g-verListt.flag=1;/给顶点置访问过的标志1verCnt+;enQueue(&q,t);p=p-next;if(verCnt=g-verts)
35、break;j=(j+1)%g-verts;/找下一个访问标志为0的顶点while(g-verListj.flag!=0)j=(j+1)%g-verts;对所有顶点和边进行访问，它的时间代价和顶点数n及边数e是相关的，它的时间复杂度是O(n+e)。图1.图的基本概念、术语3.图的遍历和连通性4.最小生成树2.图的存储5.最短路径6.AOV网和AOE网图的连通性无向图的连通性有向图的连通性无向图的连通性和连通分量：如果无向图是连通的，那么选定图中任何一个顶点，从该顶点出发，就能到达图中其他任何一个顶点。在以上的深度优先、广度优先遍历算法中具体体现为：外循环中循环条件语句while(verCntv
36、erts)中条件只会为真一次，即通过以一个顶点为起点就能访问到图中所有顶点，因此不需要再次通过这个条件进入下轮循环。如果无向图不连通，就要在图中选择不止一个起始点，即外循环下通过判断verCntverts为真进入循环的次数不止一次，且有多少次，就表示该无向图有多少连通分量。图的连通性无向图的连通性有向图的连通性有向图的强连通分量：有向图的强连通分量问题解决起来比较复杂。对一个强连通分量来说，要求每一对顶点间都有路径可达，比如顶点i和j，不光要从i能到j，还要求从j能到i。它可以利用有向图的深度优先遍历DFS通过以下算法获得：02OPTION将有向图G的所有有向边反向，构造新的有向图Gr。03O
37、PTION选取最大编号的顶点。以该顶点为起始点在有向图Gr上进行深度优先遍历。如果没有访问到所有的顶点，从剩余的那些未被访问过的顶点中选取编号最大的顶点，以该顶点为起始点再进行深度优先遍历，反复如此，直至所有的顶点都被访问到。04OPTION最后得到的生成森林中的每一棵生成树，都是有向图G的强连通分量顶点集。对有向图G进行深度优先遍历，按照遍历中回退顶点的次序给每个顶点进行编号。01OPTION如果一个有向图按照上述方法得到的强连通分量数量只有1个，就说明该有向图为强连通图。图1.图的基本概念、术语3.图的遍历和连通性4.最小生成树2.图的存储5.最短路径6.AOV网和AOE网最小代价生成树当
38、一个无向图中每条边有一个权值（如：长度、代价等），通常称为网络。如果这个无向图是连通的，且其子图满足以下4个条件：包含原来网络中的所有顶点。该子图是连通的包含原来网络中的部分边在同时满足1）、2）、3)条件的所有子图中该子图所有边的权值之和最小该子图就称为该图的最小代价生成树(Minimum Cost Spanning Tree)。一个无向连通图有n个顶点，则边数最多达n(n-1)/2，最少有n-1。生成树中就含有n个顶点和n-1条边。最小生成树Prim算法Kruscal算法普里姆(Prim)算法：对一个无向连通图G=V,E，用W表示顶点集合、U表示最小生成树中顶点集合、T表示最小生成树中边集
39、合、数组tagj表示顶点j到U集合的最短距离、数组verj记录了一个顶点的地址，这个顶点含义是：如果tagj的当前值是由边（i，j）刷新造成的，则verj=i。普里姆算法步骤：02OPTION在W中任选一个顶点u，将其移入集合U。03OPTION然后循环做如下操作：04OPTION继续下一轮循环，直到U集合中包含了所有顶点，循环结束。此时T集合便包含了最小生成树中所有的边。01OPTION初始时，W=V包含所有顶点、U和T为空，数组tag全部赋为无穷大，数组ver全部赋值为-1。A:检查u的所有仍在W中的相邻顶点v，如果边（u，v）的权值小于顶点v上的最短距离tagv，用边的权重刷新tagv的
40、值并记录verv=uB:在集合W中选择tag值最小的顶点u，将其移入集合U，并将边(veru,u)并入集合T；普里姆算法采用着眼顶点、逐次选择具有最短距离的顶点的原则来构建最小代价生成树。算法实现：typedefstructintsource;/离集合U最短时的联系点edgeTypedist;/目前离集合U的最短距离intflag;/顶点是否已经在U中的标志primNode;voidPrim(Graph*g)primNode*primList;inti,j;intcnt;/记录集合U中顶点的个数intmin;/选出的当前离集合最短的顶点intsource,dist;primList=(prim
41、Node*)malloc(sizeof(primNode)*g-verts);for(i=0;iverts;i+)primListi.source=-1;primListi.dist=MAXNUM;primListi.flag=0;/从下标为0的点开始min=0;cnt=1;primList0.dist=0;primList0.flag=1;算法实现：while(cntverts)/根据min顶点发出的边，判断是否修正相邻顶点的最短距离for(j=0;jverts;j+)if(g-edgeMatrixminj=0)/对角线元素continue;if(primListj.flag=1)/已经加入
42、集合Ucontinue;if(g-edgeMatrixminjedgeMatrixminj;primListj.source=min;算法实现：/搜索当前离集合U最近的顶点min=-1;dist=MAXNUM;for(i=0;iverts;i+)if(primListi.flag=1)continue;if(primListi.distdist)min=i;dist=primListi.dist;算法实现：/此时min一定为某个顶点的下标，如果仍然为-1表示该无相图不连通/将顶点min加入结合Ucnt+;primListmin.flag=1;printf(%d,%d),dist:%dn,pri
43、mListi.source,i,primListi.dist);算法分析：最小生成树Prim算法Kruscal算法鲁斯卡尔(Kruscal)算法：一个无向连通图G=V,E，其中V是顶点的集合，E是边的集合。010203算法开始时，令MSTV,，MST仅由图G的n个顶点构成，这n个顶点最初形成了n个连通分量，MST不包含图G的任何一条边。算法是在图G中选择权值最小的边，如果该边的加入会使MST中已有的图形成回路则放弃另选，否则将该边并入MST。反复循环，直到MST中边的条数达到n-1。在算法运行过程中，MST中的连通分量逐步减少，从最初的n个减少到最后的一个。算法思路：算法实施过程：边权值操作连
44、通分量：A,B,C,D,E连通分量标志：1，2，3，4，5（A，E）1并入MST连通分量：A，E,B,C,D1,2,3,4（A，D）1并入MST连通分量：A，E，D,B,C1，2，3（E，D）2相同连通分量标志，即存在回路、放弃连通分量：A，E，D,B,C1，2，3（C，E）3并入MST连通分量：A，E，D，C,B1,3（B，D）3并入MST连通分量：A，E，D，C，B1算法分析：假设求最小权值的边可以借助最小化堆来实现。图1.图的基本概念、术语3.图的遍历和连通性4.最小生成树2.图的存储5.最短路径6.AOV网和AOE网最短路径问题02OPTION以下称起点为源点、目的地为终点，求从源点到
45、各个终点间的最短距离称为单源最短路径问题。求各个顶点间的最短路径称为所有顶点对之间的最短距离问题。网用图来表示，其中顶点表示城市、边表示城市间公路、边的权重表示城市间的公路距离或者时间。01OPTION如：城市间的道路网最短路径Dijkstra算法Floyd算法已知加权有向图G=V,E中每条边有一个权重，且权重为非负值，其中V中的一个顶点，作为源点。问题要求找出从源点出发，到达其它各个顶点的最短路径，即到达各个顶点时所经过的路径上各条边的权值之和最小。单源最短路径问题Dijkstra算法算法的思想：设置一个顶点集合S，初始时S为空、设置每个顶点到源点的距离标签为无穷大。将源点放入S中，源点到源
46、点距离设置为0。现在以源点作为当前顶点，循环做以下操作:02OPTION在V-S集合中找到距离标签最小的顶点，将该顶点加入集合S，并以它为当前顶点，再次回到循环中。03OPTION当所有顶点都在S中时，循环结束。逐条检查当前顶点射出的边，如果该邻接点不在集合S中，且当前顶点的距离标签加上边的权值小于当前顶点的这些邻接点上的距离标签，则用当前顶点的距离标签加上边的权值刷新相邻顶点的距离标签；01OPTION每个顶点上的距离标签即其到源点的最短距离。求单源最短路径的Dijkstra算法和求最小生成树的Prim算法非常相像。算法实现：以下用邻接矩阵表示有向图：voidDijkstra(Graph*g
47、,verTypestart)primNode*DList;inti,j,m;intcnt;/记录集合U中顶点的个数intmin;/选出的当前离集合最短的顶点intsource,dist;for(i=0;iverts;i+)if(g-verListi=start)break;if(i=g-verts)exit(1);m=i;typedefstructintsource;/离集合s最短时的联系点edgeTypedist;/目前最短距离intflag;/顶点是否已经在s中的标志primNode;算法实现：DList=(primNode*)malloc(sizeof(primNode)*g-verts
48、);for(i=0;iverts;i+)DListi.source=-1;DListi.dist=MAXNUM;DListi.flag=0;以下用邻接矩阵表示有向图：/从下标为m的点开始min=m;cnt=1;DListi.source=m;DListm.dist=0;DListm.flag=1;算法实现：while(cntverts)/根据min顶点发出的边，判断是否修正相邻顶点的最短距离for(j=0;jverts;j+)if(g-edgeMatrixminj=0)/对角线元素continue;if(DListj.flag=1)/已经加入集合Scontinue;if(DListmin.di
49、st+g-edgeMatrixminjedgeMatrixminj;DListj.source=min;以下用邻接矩阵表示有向图：算法实现：/搜索距离标签最小的顶点min=-1;dist=MAXNUM;for(i=0;iverts;i+)if(DListi.flag=1)continue;if(DListi.distdist)min=i;dist=DListi.dist;/此时min一定为某个顶点的下标，如果仍然为-1表示该无相图不连通/将顶点min加入结合Ucnt+;DListmin.flag=1;以下用邻接矩阵表示有向图：算法实现：/打印顶点的最短路径和至源点的顶点序列。for(i=0;i
50、verts;i+)printf(Shorstestpathfrom%dtovertex%dis:%d.,m,i,DListi.dist);j=i;printf(Allverticesare:);while(j!=m)printf(%d-,j);j=DListj.source;printf(%d.n,m);以下用邻接矩阵表示有向图：Dijkstra算法的分析：例子中从E到D、C、F的距离分别为5、10、80，按照Dijkstra算法，可以判定最终从E到D的最短距离为5，是一个贪心算法。但如果允许有负权值，如存在边，且该边的权值为-8，则从E到D的最短路径就可能是从E到C再到D，该路径距离是2，比