《图论的几种算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《图论的几种算法ppt课件.ppt（32页珍藏版）》请在三一办公上搜索。
1、Email:,图 论 算 法,数值计算搜索法、最速下降规划方法单纯型法、匈牙利算法非数值运算搜索法、图论算法、组合优化现代优化方法遗传算法、蚁群算法、神经网络,算法分析,哥尼斯堡七桥问题从某点出发通过每座桥且每桥只通过一次回到起点,一、图的一般理论,1、起源,建模：点陆地 岛屿 边桥,一个图G由一个顶点集V和一个边的集E组成。E中每个元素e是连接顶点集 V中两个顶点u和v的边。,例:,图G=: 点集 V = v1,v2, .,vn 边集 E = e1,e2, .,em 其中 ek=vivj,图G=:其中 V = v1,v2,v3,v4,v5 E = e1,e2,e3 ,e4 e1=v1v2,e
2、2=v2v4,e3=v1v4,e4=v5v2,e1,2、定义,图的图形表示,例,联接,点的位置, 边的长度,比较: 同构,G1,G2,G3,1,2,3,4,3,4,2,1,3,4,1,2,例,（1）邻接矩阵(点点),3、矩阵表示,例,（2）关联矩阵(点边),例,4、连通性,邻接,长2,通路:,长3,长n-1,连通矩阵,l01.m,二、最短路问题,1、单源最短路问题Dijkstra,赋权图G 从点v0到其余结点的通路权和最小Dijkstra算法思想按路径长度递增顺序求最短路径算法 两个集合：S已求得最短路径的结点、V-S未确定每一步：将S 与V-S之间最短路经终点加入S存储G：带权邻接矩阵每点标
3、记 (dj, pj)：至j点最短路径的长度、前一点,Dijkstra算法流程,赋初值：w，各点与源点之间：已求Sv0,最短长度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： SSv, u= v若V-S，重复2，否则：结束,v0,v,u,d(v),d(u),w(u,v),distance,path,pathway= dijkstra(v0,w)最短路的长度、前点、路径 源点 带权邻接矩阵说明：,Matlab 程序： dijkstra.m,while kdistan
4、ce(u)+w(u,i) distance(i)=distance(u)+w(u,i); path(i)=u; end end （求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; for i=1:n for j=1:k if i=s(j) d(i)=inf; break end end end %V-S中最小距离 dmin,
5、v=min(d);,pathway=zeros(n);pathway(1:n,1:2)=v0*ones(n,1),(1:n);for i=1:n q=i; while path(q)=v0 pathway(i,2:n)=path(q),pathway(i,2:(n-1); q=path(q); endend,例,OK,l02.m,带权邻接矩阵,Floyd 算法思想带权邻接矩阵两点之间插入顶点缩短距离：构造出个矩阵D(1)、 D(2)、 、D(n-1)最后得到距离矩阵最短路径递推公式,2、每对顶点之间的最短路Floyd,带权 邻接 矩阵,例：,矩阵,两点之间：插入顶点,15通过1点,于是,15通
6、过2点,于是,按1、2会不会错过一些点？,Matlab 程序： floyd.m,%设初值D=w;path=zeros(n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endend,floyd.m,%迭代，更新D pathfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end endend,D,path=floyd(w)最短路的长度、后点 带权邻接矩阵,例,OK,l03.m,得到：最短路
7、、后点路径？,求路径,function pathway=road(path,v1,v2)%求路径：floyd的后续指令pathway=v1;q=v1;k=1;while path(q,v2)=v2 k=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,三、树,无回路的连通图: 树根, 树叶, 树枝例：,最小生成树,最短路径生成树,Kruskal 算法避
8、圈法开始： G中的边均为白色在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红；重复：直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合注：如何加边判断不形成圈？判断两端点是否属于同一子树子树：用最小标号点纪录,最小生成树,纪录两端点与边权,Matlab 程序： Kruskal.m,n=size(w,1);%求点边矩阵k=1;for i=1:(n-1) for j=(i+1):n if w(i,j)=inf b(:,k)=i;j;w(i,j); k=k+1; end endendm=size(b,2);b,I=sortrows(b,3),b=b,排序,krusk
9、al.m,树权和所在子树的 最小标号点进入最小树 的边数,for i=1:m if t(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); for j=1:n if t(j)=tmax t(j)=tmin; end end k=k+1; end if k=n break; end end,T=;c=0;t=1:n;k=1;,更新子树 的最小标号点,赋初值,不在同一子树,例,OK,l04.m,带权邻接矩阵,结果,T =1 4 2 2 4 5 3
10、 5c =17,Euler图存在一条通过所有边一次的路线的图：遍历边Th 若图 G 为欧拉图 G 连通,且所有结点度数(以此点为端点的边的个数)均为偶数中国邮路问题遍历边路最短带权图权和最小算法：FleuryHamilton图存在通过每结点一次的路线的图：遍历点国际难题旅行商问题遍历点路最短 权和最小的回路算法：改良圈算法,四、其他,二分图,匹配问题算法：匈牙利算法网络流最大流算法：Ford-Fulkerson标号算法着色图点、边、面算法：,著名算法：dijkstra floyd应用：建模竞赛 98B 灾情巡视路线07B 公交线路,说明,练习,洪水排险求区域间的邻接矩阵区域1至区域20长度不超过5的路径有多少条是否任两区域通过长度不超过5的路径均可达到,练习,某街道如图画出A点到各顶点的最短道路（最短路经生成树）,练习,某街道如图求任两顶的最短道路,练习,某街道如图欲建立有线网络连接画出此街道各顶点均相联的最短道路（最优生成树）,END,
