《图论.ppt》由会员分享，可在线阅读，更多相关《图论.ppt（125页珍藏版）》请在金锄头文库上搜索。
1、图论算法及应用图论算法及应用常州市第一中学常州市第一中学 林厚从林厚从图的概念1n图：二元组（顶点集，边集）n阶：顶点个数n有向图与无向图，入边与出边n度，入度与出度n两个顶点的邻接与非邻接、连通与非连通n孤立点，无向图中的奇点、偶点，一笔画问题n完全图：每一对顶点间都有边相连的的无向图n稀疏图与稠密图n补图：图中所有顶点和所有能使该图成为完全图的添加边所组成的图，称为原图的补图n逆图：把一个有向图的每条边都反向，由此得到的有向图1234512378654n带权图：权的含义n环：若一条边的两个顶点为同一顶点，则此边称作环n简单图：没有环、且没有多重边的图，称作简单图n路径：v1,v2,vn回路
2、：v1,v2,vn,v1n连通：从顶点vi到顶点vj有路径相连(有向图边的方向要一致)n连通图：图中任意两个顶点都是连通的n强连通图：有向图，任意两个顶点x,y间都存在着从x到y和从y到x的路径，则称此图为强连通图n连通分量：无向图的一个极大连通子图称为一个连通分量(或连通分支)，连通图唯一，非连通图不唯一n强连通分量：强连通图只有一个强连通分量，就是其自身；非强连通的有向图有多个强连通分量图的概念21234512378654n子图：取出若干顶点和边构成的新图n生成树：包含所有顶点的树状子图n最短路：从x到y的具有最小长度(路径上所有边权之和)的路n二分图：若图G的顶点集可划分为两个非空子集X
3、和Y，且满足：，且每一条边都有一个顶点在X中，而另一个顶点在Y中，那么这样的图称作二分图。n同构：两个图同构的充要条件是，两个图的结点和边分别存在着一一对应，且保持关联关系。图的概念31234512378654n点割集：点集，若G删除了后不连通，但删除了的任意真子集后G仍然连通。则称点割集。若某一结点就构成就了点割集，则称此结点为割点割点。n边割集：边集，若G删除了后不连通，但删除了的任意真子集后G仍然连通。则称边割集。若某一边就构成就了边割集，则称此边为割边或桥割边或桥。n有割点的图不一定有割边n有割边的图也不一定有割点n缩点：把没有割边的连通子图缩为一个点，此时满足：任意两点间都有至少两条
4、路径相互可达图的概念4图的存储结构1n邻接矩阵1234512378654图的存储结构2n邻接表12345213204302403556037480终点权值 指针起点1234512378654图的存储结构3n边集数组起点11234455终点23423534权值123456781234512378654图的遍历算法_深度优先搜索n特点：搜索顺序n时间复杂度:与存储结构相关n邻接矩阵：n2n邻接表：n+eDFS（depth-firstsearch）nDFS是求割点、桥、强连通分量等问题的基础n对图进行染色的思想白色：未访问灰色：访问中（正在访问它的后代）黑色：访问完毕n一般在具体实现时不必对图的顶点
5、进行染色，只需进行访访问问开开始始时时间间和和访访问问结结束束时时间间的记录即可(时时间戳间戳)，这样就可以得出需要的信息了。foreveryvertexuVGdocoloruWHITE;time0;foreveryvertexuVGdoifcoloru=WHITEthenDFS_VISIT(u);DFS（depth-firstsearch）nDFS_VISIT(u)timetime+1;dutime;/顶点u的访问开始时间foreveryedge(u,v)EGdoifcolorv=WHITEthenDFS_VISIT(v);coloruBLACK;timetime+1;futime;/顶点u
6、的访问结束时间DFS（depth-firstsearch）图的遍历算法_广度优先搜索n特点:搜索顺序n数据结构:队列n复杂度:每个元素至多进队1次，再至多访问它的关联点，所以是n2BFS(breadth-first search)nDijkstra、SPFA单源最短路径算法和Prim最小生成树算法都采用了和BFS类似的思想。n之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和末找到顶点之间的边界向外扩展，就是说，算法首先搜索和顶点s距离为k的所有顶点，然后再去搜索和s距离为k+l的其他顶点。nforeveryvertexuVGdocolouruwhite;put_in(s);/起点入
7、队whilequeuedo/队列非空就扩展foreveryvertexuchild(queuehead)doifcolour(u)=whitethenput_in(s);/队头元素的孩子未访问过，就访问并入队colour(queuehead)black;headhead+1;BFS(breadth-first search)例题1、K度路径数n给出一张无向简单图的邻接矩阵A以及正整数k，求任意两点之间长度为k的路径个数。n例如：求下图从v1到v3长度为3的路径个数。n答案为：2。例题1_求解1n利用图的邻接矩阵Ak(i,j)表示从i到j，长度为k的路径个数。n递推公式(li,j)：例题1_程序
8、fork:=2to5dofori:=1tondoforj:=1tondoforl:=1tondoAk,i,j:=Ak,i,j+Ak-1,i,l*A1,l,j;例题2、判定图的同构n给出两张图的邻接矩阵，判断他们是否同构?例题2_解法1n建立一一映射将图1的顶点与图2的顶点进行映射一个一维数组mmi表示图1中的顶点i映射到图2中的顶点mi例题2_程序1nvarA,B:array1.10,1.10ofinteger;nm:array1.10ofinteger;nn:integer;nfunctionjudge:boolean;nvari,j:integer;nbeginnjudge:=false;
9、nfori:=1tondonforj:=1tondonifAi,jBmi,mjthenexit;njudge:=true;nend;例题2_解法2(循环法)n如何产生这样的一一映射呢？n如何产生排列？form1:=1to4doform2:=1to4doifm1m2thenform3:=1to4doif(m3m2)and(m3m1)thenform4:=1to4doif(m4m3)and(m4m2)and(m4m1)then调用judge且判断;例题2_用递归法模拟循环varm:array1.10ofinteger;used:array1.10ofinteger;n:integer;proced
10、urework(d:integer);vari:integer;beginfori:=1tondoifusedi=0thenbeginusedi:=1;md:=i;work(d+1);usedi:=0;end;end;例题2_递归终止条件ifd=n+1thenbegin调用judge判断;exit;end;例题3&4、割点&割边n给出一张无向简单图，求此图的割点和割边。求割点的简单做法n删除某个顶点，判断是否仍然连通？求割点的简单做法n问题的转换:n1.是否真的需要删除顶点？n2.是否真的需要求出所有连通分量？n问题的答案:n1.否，只要将visited数组初始赋1n2.否，只要dfs一个分量
11、解答程序functionjudge(which:integer):booleanvari:integer;beginfori:=1tondovisitedi:=0;visitedwhich:=1;ifwhich=1thendfs(2)elsedfs(1);judge:=true;fori:=1tondoifvisitedi=0thenexit;judge:=false;end.求割点的经典做法n使用深度优先搜索n在搜索过程中计算每个顶点的两个值dfn和lowndfni表示DFS过程中访问顶点i的开始时间(dfs序号)nlowi表示通过其他边回到其祖先的最早时间(其子孙的最小dfs序号)，即：l
12、owi=min(lowi，lowsoni)n设DFS树上的顶点顶点v： 对其所有子孙对其所有子孙u u，都存在，都存在dfnv=lowudfnv=lowu，说明，说明v v的子孙的子孙u u不能通过其他边到达不能通过其他边到达v v的祖先。的祖先。此时如果拿掉v，则必定把v的祖先和v的儿子u及它的子孙分开，于是v v便是一个割点便是一个割点，v和它的子孙形成一个块(没有割点的连通子图)。求割点的求割点的动画演示动画演示 如果对于如果对于某一个子孙某一个子孙u u，存在，存在 dfnvlowudfnvu前检查它的id是否在上一次u-v时被标记，这样如果两点之间有多条边时，每次遍历都只标记其中一条
13、，还可以通过其他边回去，形成第二条新的路。经典做法求割边的经典做法求割点的时候，维护一个栈st每遍历到一个顶点v则把它放进去，对它的子孙u如果dfnu为0，则表示还没有遍历到则先DFS(u)，之后再判断lowu和dfnv，如果lowu=dfnv，则把栈中从栈顶到v这一系列元素弹出，这些点与v形成一个块，如果u的子孙x也是一个割点，这样做会不会错把它们和v，u放在一起形成一个块呢，这种情况是不会发生的，如果发现x是一个割点，则DFS到x那一步后栈早就把属于x的子孙弹出来了，而只剩下v，u的子孙，它们之间不存在割点，否则在回溯到v之前也早就提前出栈了！画一个图照着以下代码模拟一下可以方便理解。 求
14、割点的时候由于不知道树根是不是只有一个儿子，这样在求割点的时候由于不知道树根是不是只有一个儿子，这样在DFSDFS过来中不会满足过来中不会满足lowu = dfnvlowu = dfnv而判为割点，但有两个或两而判为割点，但有两个或两个以上儿子的根肯定也是一个割点，所以要特判！个以上儿子的根肯定也是一个割点，所以要特判！voidCutBlock(intv)dfnv=lowv=+cnt;st+top=v;for(inti=pv;i!=-1;i=edgei.pre)intu(edgei.d);if(dfnu=0)CutBlock(u);GetMin(lowv,lowu);if(lowu=dfnv)
15、/V是一个割点block0=0;while(true)block+block0=sttop;if(sttop-=u)/只能弹到u为止，v还可以在其他块中break;block+block0=v;/割点属于多个块，一定要补进去Count(block);elseGetMin(lowv,dfnu);/割边和缩点割边和缩点voidCutEdge(intv,intfa)dfnv=lowv=+cnt;st+top=v;for(inti=pv;i!=-1;i=edgei.pre)intu(edgei.d);if(u=fa)continue;if(!dfnu)CutEdge(u,v);GetMin(lowv,
16、lowu);if(lowudfnv)/边v-u为一条割边cutE+numE=E(v,u);/将u及与它形成的连通分量的所有点存起来+numB;while(1)idsttop=numB;if(sttop-=u)break;elseGetMin(lowv,dfnu);例题5、求有向图的强连通分支n经典算法有两个：1、Tarjan算法：只需要一次DFS和维护一个栈便可以，实现简单，参见下一页的程序及注解，详细描述见附文。2、Kosaraju算法：基于两次DFS，代码量偏大但容易理解，时间复杂度为O(n+m)，效率高！但是需要把边反转，有点麻烦。下面会详细分析。voidTarjan(intv)dfnv
17、=lowv=+num;usedv=1;st+numSt=v;for(inti=pv;i!=-1;i=edgei.pre)intu(edgei.d);if(!dfnu)/还没有标号的点Tarjan(u);/先遍历它的子结点GetMin(lowv,lowu);/用子结点更新当前点的low值elseif(usedu&GetMin(lowv,dfnu);/used判断点是否在栈中if(dfnv=lowv)scc+;while(1)intu(stnumSt-);idu=scc;usedu=0;if(v=u)break;与求割点和割边的程序相比，上面的程序多出了红色的一行红色的一行，为什么呢？看下面这个图
18、来解释。根据dfn可以看出搜索的顺序是1-2-5-6形成一个强连通分量(2,5,6)，于是开始退栈,回溯到1从3出发到达4,此时如果直接用dfn2更新low4的话，会得到low4=2,变小后而与dfn4不再相等，不能退栈，这与最后的4形成一个单独强连通分量是不符合的，所以，不在栈中的点，不能用来更新当前点的low值，为什么无向图不用标记呢，那时因为，边是无向的，有边从4-2同时也必有边2-4由于2之前被标记过，而遍历到当前结点4又不是通过w(2,4)这条边过来的，则必还存在另一条路径可以使2和4是相通的，(即图中的4-3-1-2),从而2,4是双连通的。其实，以上三个算法都源于Tarjan，只
19、是根据dfn和low判断条件不同而得到不同的结果，所以Tarjan算法超强！Kosaraju算法n(1)第一次对图G进行DFS遍历n遍历中，记录所有点的退出顺序nDFS遍历的顺序：n所有点的退出顺序：1 12 25 54 43 35324112355321441n(2)改变每一条边的方向，构造出一个新图Gn然后按照退出顺序的逆序进行第二次DFS遍历n所有遍历到的点就是一个强连通子图532411 12 25 54 43 3Kosaraju算法n按照1、4、2、3、5的顺序进行DFS遍历n1、4为一个强连通子图n2、3、5为一个强连通子图5324114退出退出253退出退出1 12 25 54 4
20、3 3Kosaraju算法n简单证明：n充分性：如果存在两点A和B能够互相到达，则第二次DFS遍历中必然能从一个点搜到另一个点，归于同一个强连通子图。n必要性：如果存在两点A和B，只能从A到B而不能从B到达A，则在第一次DFS遍历图G时，B必然比A先退出。那么在第二次DFS遍历图G时，B是无法到达A的。Kosaraju算法无向图传递闭包n无向图的传递闭包主要用于判断图的连通性和图中满足条件的连通分支，具有很高的实用价值。Floodfilln顾名思义，Floodfill的功能是填充一个有界区域，可以用于求无向图传递闭包。nFloodfill可以用DFS或者BFS实现，若v在连通块中，对于与v相连
21、的点u都加入这个连通块。例题6、Castle一座城堡被分成*个方块（m50，n50），每个方块可以有04堵墙（0表示无墙）。图示给出了建筑平面图：图中的加粗黑线代表墙。几个连通的方块组成房间，房间与房间之间一定是用黑线（墙）隔开的。现在要求你编一个程序，解决以下三个问题：1、该城堡中有多少个房间；2、最大的房间有多大；3、拆除城堡中的哪一堵墙(城堡最外一圈的围墙不能拆)，以形成一个尽可能大的房间。例题6_分析n本题实际上是无向图的连通问题。n把每个方块看成一个点。n如果两个相邻的方块之间没有墙，就在这两个方块表示的点之间连一条边。n第一问求的实际上就是这个图有多少个连通分量。n第二问求的是结点
22、数最多的连通分量。n第三问只要穷举要拆的墙，然后把相邻的连通分量所包含的结点数相加，取最大即可。拓扑排序_定义n对一个有向无有向无环图(Directed Acyclic Graph，简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若 E(G)，则u在线性序列中出现在v之前。n应用价值：工程的安排、课程的安排等。nC1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7nC1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6n以上两个均为该图的拓扑序列拓扑排序_举例拓扑排序_应用n若将图中顶点按拓
23、扑次序排成一行，则图中所有的有向边均是从左指向右的。n一个DAG的拓扑序列通常表示某种方案切实可行。n若图中存在有向环，则不可能使顶点满足拓扑次序。n作为某些算法的预处理过程(如DP、递推)。拓扑排序算法_无前趋顶点法n该方法的每一步总是输出当前无前趋(即入度为零，若有多个则不计次序)的顶点。n从G中选择一个入度为0的顶点v加入到拓扑序列中，从G中删去v及其所有出边（其实只需要更新边尾节点v的入度）。n如果最后发现输出的顶点数小于|V|，则表明有回路存在。拓扑排序_存储结构n为便于考察每个顶点的入度，可保存各顶点当前的入度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有
24、入度为零的顶点：在开始排序前，扫描对应的存储空间，将入度为零的顶点均入栈(队)。以后每次选入度为零的顶点时，只需做出栈(队)操作即可。nforeveryvertexudoifdegreeu=0thenput_in(v)whilequeuedoforeveryedge(queuehead,v)EGdodec(degreev)ifdegreev=0thenput_in(v)inc(head)ifnotallvertexudegreeu=0thenNosolution!/或者输出的顶点数小于总的顶点数，输出无解（回路）拓扑排序_算法实现n简单&高效&实用的算法。n复杂度O(V+E)。拓扑排序_算法效
25、率例题7、Soldiern有n个士兵（1n26），编号依次为A、B、C， 队列训练时，指挥官要把一些士兵从高到矮依次排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得“p1比p2高”这样的比较结果（p1，p2A，Z），记为p1p2。例如AB，BD，FD。士兵的身高关系如图所示：n 对应的排队方案有三个：AFBD、FABD、ABFD。ABDF最短路径_定义n在带权图G=（V，E）中，若顶点 Vi,Vj是图G的两个顶点，从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和。从顶点Vi到Vj可能有多条路径，其中路径长度最小的一条路径称为顶点Vi到Vj的最短路径。 n对于不带权的图，只要认
26、为每条边权值是1，即可当作带权图一样处理了。n单源最短路径(Single-sourceshortestpath) 从某个顶点（源点）到其它顶点（终点）的最短路径。n多源最短路径(AllPairsShortestPaths) 求图中每一对顶点间的最短路径。最短路径_问题分类最短路径_朴素算法nDFSnBFSn展开所有的路径，从中选择最短的。显然这两种算法的效率比较低下。可以通过剪枝进行优化，在此不多做介绍。边的拓展（松弛操作）n如果存在一条从u到v的边，那么从s到v的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是distu+w(u,v)。如果这个值比目前已知的
27、distv的值要小，我们可以用新值来替代当前distv中的值。边的拓展（松弛操作实现）nprocedurerelax(u,v,w:integer);/多数情况下不需要单独写成nbeginnifdisu+wdisvthennbeginndisv:=disu+w;nprev:=u;nendnend;最短路径算法1_Dijkstran用于求解单源最短路径问题。n不能处理图中有负环的情况，而且所有边权要非负。n有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)。 Dijkstra算法分析_初始状态n算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。n源点s的
28、路径长度值被赋为0（dists=0）。n同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中除s外的所有顶点v，distv=）。Dijkstra算法分析_核心思想n算法维护两个顶点集S和Q。集合S保留了我们已知的所有distv的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的distu值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。Dijkstra算法分析_代码实现n初始化： for each v(vV,vs):disv=maxint;
29、 diss=0; pres=s; S=s;nFor i:=1 to n 1.取V-S中的一顶点u使得disu=mindisv|vV-S 2.S=S+u 3.For V-S中每个顶点v do Relax(u,v,W(u,v)n算法结束：disi为s到i的最短距离； prei为i的前驱节点Dijkstra算法_复杂度分析及优化nDijkstra每次从集合V移动一个点到集合S，外层循环的运行次数为n。n循环内的复杂度取决于函数min()的复杂度。n如果扫描V中的每个点，选取dist值最小的点，复杂度为O(n)，整体复杂度为O(n2)。n使用二叉堆来实现每步的min操作，则算法复杂度从O(V2)降到O
30、(V+E)V)。推荐对稀疏图使用。n适用条件&范围：n单源最短路径(从源点s到其它所有顶点v);n有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);n边权可正可负(如有负权回路输出错误提示);n差分约束系统;最短路径算法2_BellmanfordBellmanford_算法描述n对每条边进行|V|次Relax操作;n完成后:如果存在(u,v)E使得disu+w(u,v)disv,则存在负权回路;否则,disv即为s到v的最短距离,prev为前驱。nFori:=1to|V|doFor每条边(u,v)EdoRelax(u,v,w);For每条边(u,v)EdoIfdisu
31、+wdistqueuehead+wqueuehead,vthendistvdistqueuehead+wqueuehead,vifnothashvthenput_in(v);hashvtruehashqueueheadfalseinc(head)SSSP On DAGn 适用条件&范围： DAG(有向无环图)；边权可正可负；n 算法描述： 1、Toposort； 2、If Toposort=False Then HALT(Not a DAG)； 3、For 拓扑序的每个顶点u do For u的每个邻接点v do Relax(u,v,w); 算法结束后：如有环则输出错误信息；否则disi为s到
32、i的最短距离，prei为前驱顶点。n 算法分析： 时间复杂度O(V+E)，时间&编程复杂度低，遇到符合条件的题目(DAG)，推荐使用。 此算法的步骤3可以在toposort中实现，这样即减小了此算法复杂度的一个系数。最短路径算法4_FloyednFloyd-Warshall 算法适用场合： 找出每对点之间的最短距离 稠密图效果最佳 边权可正可负n它需要用邻接矩阵来存储边，通过考虑最佳子路径来得到最佳路径。 n注意单独一条边的路径也不一定是最佳路径。Floyed_算法思想n从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大（两点不连通）。对于每一对顶点 u 和 v，看看是否存在一个顶
33、点 w ，使得从 u 到 w 再到 v 比己知的路径更短，如果是更新它。Floyed_算法实现n初始化：disu,v=wu,vnFork:=1tonFori:=1tonForj:=1tonIfdisi,jdisi,k+disk,jThenDisi,j:=disi,k+disk,j;n算法结束：dis即为所有点对的最短路径矩阵Floyed_算法分析及优化n 此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。时间复杂度O(n3)。n 考虑下列变形：如果(i,j)E，则disi,j初始为1,否则初始为0，这样的Floyd算法最后的最短路径矩阵即成为一个判断
34、i,j是否有通路的矩阵。n 更简单的，可以把dis设成boolean类型，则每次可以用“disi,j:=disi,jor(disi,kand disk,j)”来代替上述算法中的红色部分，可以更直观地得到i,j的连通情况。n 与Dijkstra算法类似，算法中红色部分可以加上对Pre数组的更新。例题8、Shortn平面上有n个点（n=100），每个点的坐标均在-1000010000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。例题8_分析例题9、ProjectnSERCOI工程组是
35、一个讲究效率的工程小组。为了规划和管理的方便，他们将一个工程分为若干个项目，每个项目都可以独立进行。所有项目都工作完毕时，整个工程也就完成了。每个项目都需要一定的工作时间。工程最后总耗时是从第一个项目开始到最后一个项目结束的这段时间。n各个项目之间可能存在也可以不存在相互制约关系。如果有制约关系，则可能是以下四种之一（设两个项目分别为p和q)：n（1）SASpq(pSartAfterqStart）n（2）FASpq(pFinishAfterqStart）n（3）SAFpq(pSartAfterqStart）n（4）FAFpq(pFinishAfterqStart）n如果没有制约关系，则可同时进
36、行。n要求总时间最少？例题9、Project例题9_分析最小生成树_定义n对于连通的带权图G，其生成树也是带权的。生成树各边权值总和称为该树的权。权最小的生成树称为G的最小生成树(MST，Minimum Spanning Tree)。n解决最小生成树问题一般有两种算法Prim和Kruskal 。最小生成树算法1_Prim算法nPrim算法基于一种贪心策略：每次选取离当前点集最近的点加入MST。n这种贪心可以证明是正确的，详细证明可以参阅算导。n初始时，MST是只包含一个点的集合，由于每个点最终都要被包含在MST内，所以Prim算法可以由图中的任意一点开始。n初始化：disv=maxint(vV
37、,vs);diss=0;pres=s;S=s;tot=0；nFori:=1ton1.取顶点vV-S，使得W(u,v)=minW(u,v)|uS,vV-S,(u,v)E2.S=S+v;tot=tot+W(u,v);输出边(u,v)；3.ForV-S中每个顶点vdoRelax(u,v,W(u,v)；n算法结束：tot为MST的总权值最小生成树算法1_Prim算法实现注意：这里的Relax不同于求最短路径时的松弛操作。它的代码如下：procedurerelax(u,v,w:integer);beginifwdisvthenbeginprev:=u;disv:=w;end;end;可以看到，虽然不同，
38、却也十分相似。最小生成树算法1_Prim算法实现n不难发现，Prim算法和Dijkstra算法惊人的相似，不同之处只在于dist数组的含义，在Dijkstra中dist表示点到源点s的距离，而Prim中dist表示点到点集MST的距离，请小心区分。另外就是松弛操作和输出不大一样。n与Dijkstra一样Prim算法也可以用堆来优化Extract_Min函数。 算法复杂度从O(V2)降到O(V+E)V)，推荐对稀疏图使用。最小生成树算法1_Prim算法分析u适用范围：无向图(有向图的是最小树形图)多用于稀疏图边已经按权值排好序给出最小生成树算法2_Kruskal算法Kruskal_算法思想n每次
39、选不属于同一连通分量(保证无圈)且边权值最小的两个顶点，将边加入MST，并将所在的两个连通分量合并，直到只剩一个连通分量。n将边按非降序排列(Quicksort,O(EE)nWhile 合并次数少于|V|-1 Do 取一条边(u,v)(因为已经排序，所以必为最小) If u,v不属于同一连通分量 then 合并u,v所在的连通分量 输出边(u,v) 合并次数增1 tot=tot+W(u,v)n算法结束：tot为MST的总权值Kruskal_算法实现n检查2个顶点是否在同一连通分量可以使用并查集实现(连通分量看作等价类)。n算法主要耗时在将边排序上。n优化方法：O(n)时间关于边权建二叉小根堆；
40、每次挑选符合条件的边时使用堆的DelMin操作。这种方法比用Qsort预排序的方法稍微快一些，编程复杂度基本一样。n另外，如果边权有一定限制，即=某常数c，则可以使用线性时间排序以获得更好的时间效率。Kruskal_算法分析及优化例题10、Wiren学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们时间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。n当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算
41、机的连接。 n现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）。例题10_分析另类MST算法n由生成树的定义可以知道：1)在一个生成树上另外加上任意一条边，必然形成一个环。2)在这个环中删除一条边后，剩下的边必然仍能形成一棵生成树。n另类MST算法对于一棵任意的生成树，向其中加入任意一条边，并删除形成的环中最大的一条边。可以保证新的生成树必然比原有的生成树小。n不断重复上述操作，直到图中所有的边都被尝加入过生成树中，最后得到的生成树一定是MST。另类MST算法n由于另类MST算法不断动态的维护生成树，它相对于前面介绍的MST算法，优势在于可以处理动态的MST
42、问题。n但是另类MST算法时间复杂度和编程复杂度相对于Kruskal和Prim都要大的多，在这里只是做一下简单介绍。另类MST算法树型动规n一些基于图论基础(遍历)的动规题目：骑士（2008年浙江省选二试）树的路径覆盖叶子的颜色骑士（2008年浙江省选二试）n有n个点，每个点都指定了一个不能共存的点。n选一个可行点集，求最大点权值和。nn点n边的图，求一个权值之和最大的点集，要求点集中的点之间没有边相连。骑士（2008年浙江省选二试）n把每个连通块分开处理。n一个连通块中，可以看作是多棵树，所有树的根构成一个环。骑士（2008年浙江省选二试）n可以从一个环上的点向下DFS遍历n但是这样要预处理
43、边，很麻烦骑士（2008年浙江省选二试）n可以从叶节点开始，不断的更新父亲n这样就能直接用输入的信息处理n把所有的叶节点放入队列，进行类似宽搜的扩展，每次把一个叶节点取下，如果其父亲变成了叶子，则放入队列。骑士（2008年浙江省选二试）n用fu,0表示以u为根的子树，不取u节点的最大权值和。nfu,1表示取u节点。n对于u的父亲vnfv,0=fv,0+max(fu,0,fu,1)nfv,1=fv,1+fu,0骑士（2008年浙江省选二试）n减少v的入度，如果入度为0，说明v变成了叶节点，加入队列。n直到队列为空时，就只剩下一个环了。骑士（2008年浙江省选二试）fori:=1tondoifpi
44、=0thenbegin/初始队列，如果入度为0，就放入队列inc(l);zl:=i;end;whilerldobegin/宽度优先搜索inc(r);a:=zr;inc(fa,1,xa);/如果取点a，增加点a的权值inc(fya,1,fa,0);/更新父亲inc(fya,0,max(fa,0,fa,1);dec(pya);/减少父亲的入度ifpya=0thenbegin/如果成为叶节点，放入队列inc(l);zl:=ya;end;End;骑士（2008年浙江省选二试）n剩下对环的处理n枚举一个点的状态，然后断开这点相连的一条边，用简单的动规转移就可以了骑士（2008年浙江省选二试）n回顾算法，
45、我们用了宽度优先搜索的顺序动规代替了深度优先，让算法实现起来更简单方便。n这种方法同样适用于一些存在拓扑序的图上的动规问题。树的路径覆盖n给出一棵树，求一个路径的集合，使得每个点有且仅有一条路径覆盖它，问最少需要多少条路径。n特别的，一个点也可以认为是一条路径。树的路径覆盖n用j表示节点i在路径中的入度，fi,j表示节点i的入度为j时以i为根的子树的最小路径覆盖。n用宽度优先搜索不断更新叶节点。树的路径覆盖n对于一个叶节点u，其父节点为v，执行一下更新：nfv,0=fv,0+fu,2nfv,1=min(fv,1+fu,2,nfv,0+min(fu,0+1,fu,1)nfv,2=min(fv,1
46、+fu,2,nfv,1+min(fu,0,fu,1-1)树的路径覆盖nfi,j表示节点i的入度为j时以i为根的子树的最小路径覆盖。n每次更新意味着把一棵子树连到节点i上。n所以所谓的子树不是在原图中的子树，而是会不断增加节点的一棵临时子树。树的路径覆盖n每个叶节点只需删除一次n效率O(n)叶子的颜色n一棵树，已知每个叶节点的颜色，只有白或黑两种颜色。n把一些点染色后，每个叶子节点的颜色就是从根到这个叶节点的路径上最后一个染色节点的颜色。n最少需要给多少个节点染色。白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n从叶子开始更新n用fi,0表示i节点染成白色，满足以i为根的子树最少的染色节点数
47、。n用fi,1表示i节点染成黑色。n为什么没有不染色的状态？白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n显然根染色一定不会比不染色的情况差。n初始化所有叶节点nfi,最终颜色=1nfi,另一种颜色=maxlongint白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n对于一个u的父亲vnfv,0=fv,0+min(fu,01,fu,1)nfv,1=fv,1+min(fu,11,fu,0)白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n一棵树，已知每个叶节点的颜色，只有白或黑两种颜色。把一些点染色后，每个叶子节点的颜色就是从根到这个叶节点的路径上最后一个染色节点的颜色。n可以任意选
48、定一个节点作为根，再染色，求最少染色数。白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n可以证明随便选择一个点为根，都可以求出最少的染色节点数。白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n假设最优解的根为u，显然u的周围不会有和它相同的颜色节点。n如果把根移动到一个u的相邻节点，如果是这个节点一个空节点，则染成和u原来的同色，去掉u的染色，同样也是一个最优解。白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n如果是这个节点一个与u不同色的节点，则所有的颜色都不需要改变，仍然是一个最优解。白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n一棵树，已知每个叶节点的颜色，只有白或黑两
49、种颜色。把一些点染色后，每个叶子节点的颜色就是从根到这个叶节点的路径上最后一个染色节点的颜色。n可以任意选定一个节点作为根，再染色，求染色点的最小权值和。白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n修改状态表示。n0无色1白色2黑色nfv,0=fv,0+min(fu,0,fu,1,fu,2)nfv,1=fv,1+min(fu,0,fu,1du,fu,2)nfv,2=fv,2+min(fu,0,fu,2du,fu,1)白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n初始化n只有颜色对上的值为dun其他都不可行，赋值无穷大。白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n必须对每个点为根的情况都求一次，需要O(n2)吗？n有很多重复的操作，要怎么设计算法才能避免重复呢？白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n先随便选取一个节点作为根节点，求出最优值。n然后把这个根移动到一个相邻的位置，可以用O(1)的时间进行最优值的维护。白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n把根变成树上一个节点，就是在树上拆下一棵子树，一个节点变成根，就是增加一棵子树。白白白白黑黑黑黑白白白白白白白白黑黑黑黑叶子的颜色n这个算法就是用一个虚拟的根在树上进行深度优先遍历，我称之为假根遍历。n最终效率还是O(n)白白白白黑黑黑黑白白白白白白白白黑黑黑黑
