图论中的程序设计.ppt
《图论中的程序设计.ppt》由会员分享,可在线阅读,更多相关《图论中的程序设计.ppt(122页珍藏版)》请在三一文库上搜索。
1、2019/11/15,第4次课 图论中的程序设计,上海大学计算机工程与科学学院,主要内容,1 图论算法基础 1.1 连通性 1.2 最小生成树 1.3 最短路径 1.4 有向图的传递闭包 1.5 回路问题 1.6 Bellman-ford 算法与负权回路 1.7 第n最短路径问题 2 实例研究,基本概念,图:图G是由顶点集合及顶点间的关系集合组成的一种数据结构:G( V,E ),其中,V是顶点集,E是边关系(或边集合)。 有向图:在图G中,如果表示边的所有顶点对(x,y)是有序对,那么称G是有向图,有序对称为有向边,x称为有向边的起点,y称为有向边的终点。 无向图:如果图G中表示边的所有顶点对
2、(x,y)是无序的,那么称G是无向图。 子图:设有两个图G(V,E)和G(V,E)。如果VV 且EE,那么称图G是图G的子图。,1 图论算法基础,1.1 连通性 1无向图的深度优先生成树(森林) 2割点与互连通块 3无向图的割边 4有向图的深度优先生成树(森林),一些概念,路径 :若从顶点u出发,沿某些边经过一些顶点v1,v2,vm,到达顶点v,则称顶点序列(u,v1,v2,vm,v)为从顶点u到顶点v的路径。 顶点u到v可达:如果存在一条从u到v的路径,那么称顶点u到v是可达的。 回路:起点终点重合的路径 设G为无向图 连通图:对无向图G,如果G的任何两个顶点都是相互可达的,那么称G是连通的
3、。 连通分支:图G的连通分支G是G的极大连通子图。当G只有一个连通分支时,G本身是连通的。,一些概念(续),设G为有向图 单向连通:如果G的任何两个顶点中,至少从一个顶点到另一个顶点是可达的,那么称G是单向连通的。 强连通:如果G的任何两个顶点都是相互可达的,那么称G是强连通的。 强连通分支:如果G是G的子图,G是强连通的,并且不存在G的真子图G,使G是强连通的,且G以G为真子图,那么称图G为图G的强连通分支 。,1. 无向图的深度优先生成树,(1)无向图G的深度优先遍历搜索过程 设当前访问的顶点为u,检查是否有与u关联的尚未通过的边e。如有,设为e=(u,v),若v未访问,则从u前进到v,将
4、(u,v)标上“通过”标记。若v已访问,则将边(u,v)标上“通过”标记。如果与u关联的所有边均已通过,那么从u后退到u的父顶点。 通过上述搜索过程,直到与u0关联的所有边都通过为止。再继续选G中未访问过的顶点重复这种遍历方式。最终得到G的深度优先生成树(或森林)。 (2)深度优先数:对G进行深度优先遍历时对访问的顶点u顺序编号,记为 DFN(v) (3)算法复杂性为O(max(|V|,|E|)。,无向图的深度优先搜索示例,深度优先搜索图,2. 割点与互连通块,U为G的点割集:G是连通图,UV,如果从G中删除U中的所有顶点后得到的图不再连通,但U的任何真子集均无这一性质,那么称U为G的点割集
5、。 割点:当点割集为单元素集合v时,称v为G的割点。 互连通图:不含割点的图。,关于割点的两条结论,设G为连通无向图,r是深度优先生成树的根。那么顶点r是图G的割点,当且仅当,r至少有两个儿子顶点。 设v不是深度优先生成树的根。那么,v是图G的割点,当且仅当,v的所有后裔都没有后退边与v的祖先顶点相连。,在深度优先搜索时,定义每个顶点的低位数L(v) : 从该顶点v出发,只用最多一条回头边,沿有向边能走到的顶点中DFS数最小值。 低位数L(v)的两种情况: 没用上回头边,则能走到的DFS数最小的的顶点就是该点自身,对应的路是一个顶点构成的平凡的路。此时L(v)=DFN(v)。 用了回头边,则一
6、定是最后一条边是回头边,走到一个DFS数更小的顶点。此时L(v)=DFN(v)。,低位数L(v),无向图,深度优先搜索图,低位数搜索图,最低深度优先数Lu,Lu是从u沿着深度优先树的某后裔最多有一条后退边所能到达的顶点的集合。,Lu计算过程: if (u 是第一次访问) then Lu=DFNu; for all后退边(u,v) do Lu=min(Lu,DFNv); for all向前边(u,v) if (v访问结束) do Lu=min(Lu,DFNv);,割点求解思路,对根节点,即DFS数为1的顶点,其为割点当且仅当在DFS树中有两个或以上子节点; 其余所有非根节点v是割点的充分必要条件
7、是:v存在一个子节点u(在DFS树中的子节点)满足即L(u)=DFN(v)。 前面图中,圈外数字标出的顶点的低位数(注:没标圈外数字的顶点低位数和DFS数相等),绿色顶点为割点。,求割点和互连通块的算法,设定: 设G为连通图G=(V,E) 通过设定一个栈Stack,存放访问过的边;采用标记函数DFNu、Lu。 访问标志Flagu: Flagu=0表示未访问 Flagu=1表示已访问。 U的父顶点标记为Prevu。,求割点和互连通块的算法(1),S1:for all uV Do Prevu=0; Flagu=0; End Do; i=1;Stack=; S2:for k from 1 to n
8、Do 若存在未访问的顶点k,则 Do 取u=k; i=1; DFNu=i, Lu=i, Flagu=true; sp=0;End Do; 转S3; S3: 若与u关联的边不存在,则u是孤立点; 否则重复做以下工作,求割点和互连通块的算法(2),S4:当与u关联的未通过的边(u,v)存在时,重复做以下工作 Do 边(u,v)入栈Stack;将边e=(u,v)标记“通过”; 如果结点v未访问过,那么 Do i=i+1; DFNv=i;Lv=i;Prevv=u;Flagv=1; 将(u,v)标记“树枝“;取后继结点,即u=v End Do 如果结点v已访问过,那么 /后退边 Do 如果LuDFNv,
9、那么做调整Lu=DFNv; End Do End Do; 转S5;,求割点和互连通块的算法(3),S5:如果Prevu不为0(即u不是根),那么 Do 若(Lu = DFNPrevu),则 Do 将Stack中从栈顶起的边元素e1、e2、ek-1、ek=(F(u),u)退出栈Stack; /这些边构成一个互连通块 若Prevu不是根,则Prevu是一个割点; End Do 若LPrevuLu,则调整LPrevu=Lu; 回退,即取u=Prevu; End Do 若u是根结点,则 Do 检查u是否连结两条树枝,判定是否是一个割点; 若与u关联的边都访问过了,退出循环;否则转S4 End Do E
10、nd Do End Do,求割点关键代码,void DFS(int cur,int par) dfncur=lowcur=+Index; int size=adjcur.size(), cnt=0; for(int i=0;ilowv) lowcur=lowv; if(cur=root ,3. 无向图的割边,边割集:设EE,如果从G中删除E的所有边后所得的图是不连通的,但E的任何真子集均无此特性,那么E为G的边割集或割集。 割边:当割集为单元素集e时,称e为割边,注意: 不是所有的图都有割边,如顶点数至少是3的完全图无割边。 由一条线段构成的图有一条割边,去掉这一条边后留下了两个孤立的点。 由
11、一个点构成的单点图无割边。,割边的关键特征:对于边,v是u的儿子,如果儿子v及儿子的子孙均没有指向u的祖先的后向边时,是割边。 LOWvDFNu,void CutEdge(int cur,int par) dfncur=lowcur=+Index; for(int i=headcur; i; i=bufi.next) int v=bufi.v; if(v=par)continue; if(!dfnv) CutEdge(v,cur); if(lowcurlowv) lowcur=lowv; if(lowvdfncur) ansnAns+=bufi.id; else if(lowcurdfnv)
12、lowcur=dfnv; ,求割边代码,练习:求Lv值及求图的割点,求割点的题 POJ 1144 Network POJ 2125 Destroying The Graph,POJ 1815 Friendship (字典序最小的点割集) POJ 3204 Ikkis Story I - Road Reconstruction (找关键割边) POJ 3308 Paratroopers POJ 3084 Panic Room POJ 2987 Firing (最大权闭合子图) POJ 3469 Dual Core CPU POJ 1966 Cable TV Network (无向图点连通度) H
13、DU 1565 方格取数(1) (最大点权独立集) HDU 1569 方格取数(2) (最大点权独立集) HDU 3046 Pleasant sheep and big big wolf HOJ 2811 Earthquake Damage (最小点割集) ZOJ 2587 Unique Attack (最小割的唯一性判定) ZOJ 2539 Energy Minimization ZOJ 2930 The Worst Schedule ZOJ 2532 Internship (找关键割边),练习题,4. 有向图的深度优先生成树(森林),一些概念 树枝:属于DFS树的边; 后退边(u,v):(
14、u,v)T,但u是v的后裔,DFNvDFNu; 向前边(u,v):(u,v)T,但v是u的后裔,DFNuDFNv; 横跨边(u,v):(u,v)T,但v不是u的后裔,DFNuDFNv。,标记函数LLu,命题: 设G=(V,E)是有向图,那么v是G的强连通子图的生成树的根结点,当且仅当,LLv=DFNv。 证明:略,记S(u)是从u出发沿DFS树最多有一条后退边或一条横跨边所能到达的点的集合。 引入新的标记函数,标记函数LLu的计算过程,求LLv的计算过程: if (v是第一次访问) then LLv=DFNv; for all后退边(v,w) Do LLv=min(Lv,DFNw); End
15、Do; for all横跨边(v,w)且w与v在同一强连通分支中 Do LLv=min(LLv,Nw); End Do; if (v的儿子结点s访问结束返回v) then LLu=min(LLu,LLs);,强连通分支的一种求法(1),标记函数DFNu、LLu如前定义,另外定义一个访问标志Flagu,父顶点标记Prevu。Flagu=0表示未访问,Flagu=1表示已访问。 算法如下: S1: for all vV Do Prevv=0; Flagv=0;Insv=0; End Do S2: i=1;S=; S3: if (存在未访问的顶点r)取u=r;else 转S8; S4: DFNu=i
16、;LLu=i;Flagu=1;u入栈,Insu=1;,强连通分支的一种求法(2),S5: Do while(存在与u关联的未“通过”的出边(u,v)) Do 将边(u,v)标记“通过”; if(Flagv=0)Do i=i+1;DFNv=i;LLv=i; Prevv=u;Flagv=1; v入栈,Insv=1;u=v; /取后继结点 End Do Else if(Flagv=1且DFNvDFNu) Do LLu=min(LLu,DFNv);End Do End while,强连通分支的一种求法(3),S6: if(Prevu0)Then Do if(LLu = DFNPu) Then Do 将
17、Stack中从栈顶起的顶点元素 v1、v2、vk-1、vk=u退出Stack; 对这些点的Ins设置0; /这些边构成一个强连通分支,同时Pu是一个割点 End Do LLPrevu=min(LLPrevu,LLu); u=Prevu; End Do While(Prevu 0)/与S5的DO配对 S7: 转S3 S8: 结束,转置图,转置图GT,GT=(V,ET),其中ET=(v,u)VV:(u,v)E,即ET由G中的边改变方向后组成。G和GT有着完全相同的强连通支,即在G中u和v互为可达,当且仅当,u和v在GT中它们互为可达。 记号:du和fu分别指深度优先搜索计算的发现时刻和完成时刻。,
18、强连通分支的另一种求法,(1)对有向图G进行深度优先遍历DFS(G),计算出每个结点u的完成时刻fu; (2)构建有向图G的转置图GT; (3)在GT中选择对应的fu最大的尚未被访问的顶点v进行深度优先遍历,结点v就成为深度优先森林中一棵新树的根。重复本工作,直到所有GT的所有顶点都访问到。 (4)输出第(3)步中产生的深度优先森林中每棵树的结点,作为各自独立的强连通分支。,图例解释,前页,图G的强连通分支为: J,K,B,E,D,C,F,H,G,I,1.2 最小生成树,设G =(V,E)是无向连通带权图,|V|n,|E|=m,E中每条边e=(u,v)的权为wuv或|e| 。 生成树:G的一个
19、子图G是一棵包含G的所有顶点的树。生成树上各边权的总和称为该生成树的耗费。 最小生成树:G的一棵具有最小总耗费的生成树。 最短树:是最小生成树问题的特例,指从G的边集合E中寻求一子集ET,使得T(V,ET)是一连通图,而且ET中边的长度之和最小。此时T必成一棵树。,1最小生成树问题,问题描述 求无向图的最小生成树。 输入 有若干个图作为测试数据。每组测试数据的第1行有两个整数n,m,其中n是图的顶点个数,m是边条数。接着的m行是每条边的描述:每行上有3个整数u,v,w,它们分别是边的两个顶点编号和边上权值,顶点编号从1开始。 输出 对每个图,输出多行内容:先输出“The all edges i
20、n the MST are”,接着输出最小生成树的各边。,最小生成树问题求法,Prim算法 Kruskal算法,1. Prim算法,Prim算法基本思想 设S,T为空集合,S用于放顶点,T用于放边。 任取一顶点,设为v1,作为起始点,让它进入集合S。 只要S是V的真子集,就作如下的选择操作: 每一次总选择一个不属于S,但和S中顶点最为接近的顶点,设为v,即选择(u,v)E,使得vS,uS,且权wuv达到最小。将(u,v)作为一树枝,放入边集合T。如此反复连续进行n-1次,此时S=V,选取到的所有边恰好构成G的一棵最小生成树T。,Prim算法过程,S1: T=;i=1,qi = -1 S2: F
21、or i from 2 to n Do pi =1; qi= di1; End do; k=1; S3: If (kn) then goto S5 S4: min= inf; /inf 表示一个极大的数; For j from 2 to n If (0qjmin) then Do Min=qj; h=j; End Do S5:T=T(h,p(h); qh = -1; S6: For j from 2 to n If (dhjqj) then Do qj =dhj; pj =h; End Do S7: k=k+1; goto S3; S8:输出T; 终止,2. Kruskal算法,Kruskal
22、算法基本思想 (1)首先将G的n个顶点看成n个孤立的连通分支,将所有的边按权(或边长)从小到大排序e1,e2,em。 (2)从第一条边开始,依边权递增的顺序查看每一条边,并按下述方法连接两个不同的连通分支: 当查看到第k条边ek=(v,w)时,若v和w分别在两个不同的连通分支T1和T2中,用边(v,w)将T1和T2连接成一个连通分支,然后继续查看第k+1条边。 若v和w在当前的同一个连通分支中,就直接查看第k+1条边(即构成圈,就放弃ek)。 这个过程一直进行到只剩下一个连通分支时为止。此时,这个连通分支就是G的一棵最小生成树。,Kruskal算法过程,S1:对属干E的边按长度进行排序,不失一
23、般性,设e1e2em。 S2:Sum=0;T ;i1;t0。 S3:若t= n-1,则转S6,否则转S4。 S4:若Tei构成一回路,则做 使i=i+l;转S4 终,否则转S5。 S5:TTei;Sum=Sum+ei;t=t+1;i=i+1;转S3。 S6:输出T,Sum;终止。,最小生成树问题主程序,int main() int n,m; /图内点的个数及边的条数 int i;NODE *Edge ; / Edgei记第i条边 while(cin n m) /读入顶点数和边数 Edge = new NODEm+1; for( i = 1;i Edgei.x Edgei.y Edgei.edg
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中的 程序设计
链接地址:https://www.31doc.com/p-4542797.html