图论算法介绍

1.最小连接问题图论算法及其应用2.最短路问题3.网络流问题4.

匹配问题1.最小连接问题问题:假设在某地区内要修建一个连接若个城镇的公路系统.己知城与之间直通公路的造价为.试设计一个造价最低的建造方案.这类问题很多,如某城市内供气系统的设计,供水系统的设计,供电系统以及通讯系统的设计等等.我们把这类问题称为最小连接问题(smallestconnectionproblem).有许多算法可用来求加权连通简单图的最小树，其中最著名的是Prim(1957)算法和Kruskal(1956)算法.制作加权简单图(G,w),其中城镇被视为G的顶点(若则认为城和城之间不可能修建公路),于是最小连接问题就转化为在(G,w)中找出一棵权和最小的支撑树.这样的支撑树称为最小树(树：不含圈的连通图).Prim算法1.任取且2.对选取3.例1

考虑图1.1(a)所示的加权图(G,w).按Prim算法构造最小树的过程图解在图1.1中，其中(b)所示的是算法的第1步；而(c)到(h)所示的是算法第2步的6次迭代，每次迭代后得到一个新顶点和一条新边(图中用线色边所示）.最后得到的最小树如图1.1(h)所示(红色的边).即各顶点标号l(x)之和).Kruskal算法1.选取3.2.最短路问题问题:假设有一个铁路系统连接着若干个城市,是该系统中的一个固定城市(比如是首都或省会城市).在该系统中试求从到其他各城市的最短路线.这个问题称为最短路问题.(shortestpathproblem)更一般的最短路问题的提法是:设(D,w)是有正值加权简单有向图,是D中的一个固定顶点.寻找从到其他顶点y且有最小权的有向路.单源点的最短路径V01001010550V1V2V5V460V32030给定带权有向图G和V0，求从V0到其余各顶点的最短路径。Dijkstra算法按照路径长度递增的次序产生最短路径源点v1…v2终点一定是V0的邻接点Vj，边一定是<V0,Vj>，它在V0的所有邻接边中最短。该路径是V0Vj1、长度最短的路径V01001010550V1V2V5V460V32030Dijkstra算法如果路径V0Vj

不是最短路径，则一定有另外一条路径，V0W…U,它比V0Vj短。但是，因为W是V0的邻接点，所以，边<V0,W>一定比边<V0,Vj>长。所以，不存在比V0Vj更短的路径。不失一般性，假设j=1Dijkstra算法它只可能有两种情况:

1）直接从源点到该点,V0X2）从源点经过顶点v1，再到达该顶点,V0V1X假设存在另外一个路径，V0WX，它比上面的路径更短。如果W≠V1，则V0W比V0WX更短，所以，要选取W，符合形式一如果W=V1，则符合形式二Dijkstra算法2、用S表示已经选取的顶点集合

S={V0,V1,V2,…Vj}下次要选取的顶点X，从V0到X的路径中经过的顶点一定都在S中。假设存在路径V0→→W→X，WS，该路径最短。因为路径V0→→W→X比路径V0→→W长，所以会选择W，而V0到W的路径中的顶点都在S中。V01001010550V1V2V5V460V32030S={V0}S={V0,V2}S={V0,V2,V4}S={V0,V2,V4,V3}S={V0,V2,V4,V3,V5}V2V5V4V3Moore-Dijkstra算法例2

考虑图1.2(a)所示的加权图(G,w).Moore-Dijkstra算法执行如下:Dijkstra算法讨论2、权值要为正数，否则，得不到正确结果1、算法的总的时间复杂度：O(v2)3、当权值出现负数时，要使用Bellman-Ford算法Dijkstra算法讨论都是从一个顶点开始都有一个距离数组D都有一个顶点是否已经被选取的标志4、和Prim算法有相似和不同的地方abcdegf195141827168213127abegf14d8c351621Prim算法产生的最小生成树Dijkstra算法讨论abcdegf195141827168213127abegf14d8c51821Dijkstra算法产生的支撑树19Dijkstra算法讨论每一对顶点之间的最短路径v0v2v1326411cab问题：给定一个图G，求出G中任意两个顶点之间的最短路径（距离和经过的顶点）解决方法：对图中的每个结点V，以V为源点，调用Dijkstra算法时间复杂度为O(v3)首先假设顶点vi和vj之间的最短路径是通过连接vi到j,的弧，然后不断的调整它从vi

到vj的所有可能存在的路径中，选出一条长度最短的路径弗洛伊德算法的基本思想是动态规划Floyd算法考察从Vi到Vj且中间顶点属于集合{V1,V2,...Vk}的所有路径，设其中最短的一条路径为P。若Vk不是路径P的中间节点，则P的所有中间顶点都属于集合{V1,V2,..Vk-1};因此从Vi到Vj且中间顶点属于集合{V1,V2,...Vk-1}的最短路径也是从Vi到Vj且中间顶点属于集合{V1,V2,...Vk}的最短路径；若Vk是P的中间节点，我们把P分解成P1={Vi,...Vk}和P2={Vk,..,Vj}，显然P1是从Vi到Vk的一条最短路径且满足所有的中间顶点均属于集合{V1,V2,..Vk-1};P2是从Vk到Vj的一条最短路径且满足所有的中间顶点均属于集合{V1,V2,..Vk-1};对任一对顶点Vi和Vj求Vi和Vj之间经过中间顶点集合{V1}的最短路径再求Vi和Vj之间经过中间顶点集合{V1，V2}的最短路径设P1是Vi到V2，且中间顶点集合是{V1}的最短路径设P2是V2到Vj，且中间顶点集合是{V1}的最短路径如果P1+P2<P(Vi,Vj)，则P1+P2是Vi到Vj的最短路径，经过的中间顶点是{V1,V2}直到求出顶点Vi和Vj之间经过{V1,V2,…,Vn}的最短路径0121200403∞121200D-1v0v2v1326411cab116200ab0caacbabc0P-1Floyd算法演示121200v0v2v1326411cab0121200403∞116200ab0caacbabc0437cabD0P0Floyd算法演示11121200v0v2v1326411cab0121200066200ab0caacbabc0437cab24abcD1P1Floyd算法演示6121200v0v2v1326411cab012120006200ab0caacbabc0437cababc235bcaD2P2Floyd算法演示采用邻接矩阵存储每对顶点之间的路径长度采用三维数组存储每对顶点之间经过的顶点Floyd算法实现1.从某个源点到其余各点的最短路径的算法2.每一对顶点之间的最短路径的算法

Dijkstra算法

Floyd算法

3.网络流问题顶点标号过程L4.匹配问题二分图的最佳匹配问题由于引入了权，所以最佳匹配不能直接套用完备匹配算法进行求解。同时，由于对最佳匹配的定义是建立在完全加权二分图的基础上的，对于不完全图，可以通过引入权为0（或是其他不影响最终结果的值），使得二分图称为完全二分图，从而使用最佳匹配算法来解决。KM算法前的准备在介绍求最佳匹配的KM算法前，首先介绍一些相关的概念：可以证明，Gl的完备匹配即为G的最佳匹配。

以此为基础，1955年Kuhn，1957年Munkres给出修改顶标的方法，使新的相等子图的最大匹配逐渐扩大，最后出现相等子图的完备匹配。这就是KM算法。KM算法一个例题某公司有工作人员x1,x2,…,xn

，他们去做工作y1,y2,…,yn

，每个人都能做其中的几项工作，并且对每一项工作都有一个固定的效率。问能否找到一种合适的工作分配方案，使得总的效率最高。要求一个人只能参与一项工作，同时一项工作也必须由一个人独立完成。不要求所有的人都有工作。一个实例Y1Y2Y3Y4Y5X135541X222022X324410X401100X512133