图论的几种算法

Email:[e-mail]图论算法数值计算搜索法、最速下降……规划方法单纯型法、匈牙利算法……非数值运算搜索法、图论算法、组合优化……现代优化方法遗传算法、蚁群算法、神经网络……算法分析哥尼斯堡七桥问题从某点出发通过每座桥且每桥只通过一次回到起点DABC一、图的一般理论1、起源ABCD建模：点——陆地岛屿边——桥一个图G由一个顶点集V和一个边的集E组成。E中每个元素e是连接顶点集V中两个顶点u和v的边。例:图G=V，E:点集V={v1,v2,...,vn}边集E={e1,e2,...,em}其中ek=vivj图G=V，E:其中V={v1,v2,v3,v4,v5}E={e1,e2,e3,e4}e1=v1v2,e2=v2v4,e3=v1v4,e4=v5v2e1v1v2v3v4v5e2e3e42、定义图的图形表示例联接点的位置,边的长度×v1v2v3v4v5e1e2e3e4比较:同构G1G2G3123434213412v1v2v3v4v5e2e3e4例1()0ijnijijAaa与点相邻否则0101110101010111010111110A（1）邻接矩阵(点点)3、矩阵表示v1v2v3v4v5e1e2e3e4e5e6e7e8例（2）关联矩阵(点边)1()0ijnmijijRrr点为边端点否则v1v2v3v4v5e1e2e3e4e5e6e7e81001100011000100011000100011000100001111R例4、连通性231,,,,nAAAA邻接长2通路:长3长n-1221nPAAAA连通矩阵v1v2v3v4v5e1e2e3e4e5e6e7e8l01.m二、最短路问题1、单源最短路问题——Dijkstra赋权图G从点v0到其余结点的通路——权和最小Dijkstra算法思想按路径长度递增顺序求最短路径算法两个集合：S已求得最短路径的结点、V-S未确定每一步：将S与V-S之间最短路经终点加入S存储G：带权邻接矩阵每点标记(dj,pj)：至j点最短路径的长度、前一点Dijkstra算法流程赋初值：w，各点与源点之间：已求S＝{v0},最短长度d=w(v0,:)、前一点p=v0u=v0更新d、p：若d(i)d(u)+w(u,i)，则d(i)=d(u)+w(u,i)，p(i)=u寻找v：V-S中使d(i)最小的v：S＝S{v},u=v若V-S，重复2，否则：结束v0vud(v)d(u)w(u,v)[distance,path,pathway]=dijkstra(v0,w)最短路的长度、前点、路径源点带权邻接矩阵说明：Matlab程序：dijkstra.mwhileknfori=1:nifdistance(i)distance(u)+w(u,i)distance(i)=distance(u)+w(u,i);path(i)=u;endend（求v*:V-S中最小距离点）k=k+1;s(k)=v;u=s(k);end%赋初值s=v0;%已求得最短路径的结点distance=w(v0,:);path=v0*ones(1,n);u=s(1);k=1;%s长dijkstra.m求v*:V-S中最小距离点%求路径%V-S中距离d=distance;fori=1:nforj=1:kifi==s(j)d(i)=inf;breakendendend%V-S中最小距离[dmin,v]=min(d);pathway=zeros(n);pathway(1:n,1:2)=[v0*ones(n,1),(1:n)'];fori=1:nq=i;whilepath(q)~=v0pathway(i,2:n)=[path(q),pathway(i,2:(n-1))];q=path(q);endend例v1v2v3v4v5869157103OKl02.m带权邻接矩阵08inf15806inf7inf609101inf903571030wFloyd算法思想带权邻接矩阵——两点之间插入顶点——缩短距离：构造出个矩阵D(1)、D(2)、…、D(n-1)最后得到距离矩阵——最短路径．递推公式(1)(1)(0)(0)()1(10)1():min{,}ijnijijijdddddD(2)(2)(1)(1)()2(21)2():min{,}ijnijijijdddddD()()(1)(1)(1)(1)(1())():min{,}nnnnnijnijijinjnndddddD2、每对顶点之间的最短路——Floyd带权邻接矩阵例：123456789101141362723541132201Inf41InfInfInfInfInf101Inf36InfInfInfInfInf10InfInf27InfInfInf4InfInf01InfInf2InfInf13Inf103InfInf35Inf62Inf30InfInfInf4InfInf7InfInfInf0InfInf1InfInfInf2InfInfInf02InfInfInfInfInf3InfInf202InfInfAInfInf541Inf20矩阵两点之间：插入顶点123456789101141362723541132201inf41...101inf3...A1——5通过1点(0)01inf41...12inf52...U于是(1)01inf41...10152...D(1)21263...10152...U1——5通过2点(2)01241...10152...D于是按1、2……会不会错过一些点？Matlab程序：floyd.m%设初值D=w;path=zeros(n);fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;endendendfloyd.m%迭代，更新Dpathfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendend[D,path]=floyd(w)最短路的长度、后点带权邻接矩阵例OKl03.m得到：最短路、后点路径？1234567891011413627235411322求路径functionpathway=road(path,v1,v2)%求路径：floyd的后续指令pathway=v1;q=v1;k=1;whilepath(q,v2)~=v2k=k+1;pathway(k)=path(q,v2);q=path(q,v2);endpathway(k+1)=v2;road.ml03.m函数——v1与v2之间路径起点辅助点循环变量起点循环：q至v2后点不是v2循环变量增加——为纪录路径增加点辅助点为新点到终点v2结束路径终点v2三、树无回路的连通图:树根,树叶,树枝例：方法：避圈法最小生成树12486223v1v2v3v4v5v612622v1v2v3v4v5v612862v1v2v3v4v5v6最短路径生成树Kruskal算法——避圈法开始：G中的边均为白色在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红；重复：直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合注：如何加边判断不形成圈？判断两端点是否属于同一子树子树：用最小标号点纪录最小生成树纪录两端点与边权Matlab程序：Kruskal.mn=size(w,1);%求点边矩阵k=1;fori=1:(n-1)forj=(i+1):nifw(i,j)~=infb(:,k)=[i;j;w(i,j)];k=k+1;endendendm=size(b,2);[b,I]=sortrows(b',3),b=b'排序kruskal.m树权和所在子树的最小标号点进入最小树的边数fori=1:mift(b(1,i))~=t(b(2,i))T(1:2,k)=b(1:2,i);c=c+b(3,i);tmin=min(t(b(1,i)),t(b(2,i)));tmax=max(t(b(1,i)),t(b(2,i)));forj=1:nift(j)==tmaxt(j)=tmin;endendk=k+1;endifk==nbreak;endendT=[];c=0;t=1:n;k=1;更新子树的最小标号点赋初值不在同一子树例v1v2v3v4v5869157103OK08inf15806inf7inf609101inf903571030Al04.m带权邻接矩阵结果T=14224535c=17Euler图存在一条通过所有边一次的路线的图：遍历边Th若图G为欧拉图G连通,且所有结点度数(以此点为端点的边的个数)均为偶数中国邮路问题——遍历边——路最短带权图——权和最小算法：FleuryHamilton图存在通过每结点一次的路线的图：遍历点——国际难题旅行商问题——遍历点——路最短→权和最小的回路算法：改良圈算法四、其他二分图匹配问题算法：匈牙利算法网络流最大流算法：Ford-Fulkerson标号算法着色图点、边、面算法：著名算法：dijkstrafloyd应用：建模竞赛98B灾情巡视路线07B公交线路说明练习洪水排险求区域间的邻接矩阵区域1至区域20长度不超过5的路径有多少条是否任两区域通过长度不超过5的路径均可达到练习某街道如图画出A点到各顶点的最短道路（最短路经生成树）☆A13421612314256321练习某街道如图求任两顶的最短道路☆A13421612314256321练习某街道如图欲建立有线网络连接画出此街道各顶点均相联的最短道路（最优生成树）☆A13421612314256321END