无向图传递闭包.ppt

无向图的传递闭包无向图的传递闭包主要用于判断图的连通性和图中满足条件的连通分支,具有很高的实用价值。借鉴无向图的传递闭包思想,可以计算图中每一对顶点之间的最短路径(实际上就是 Floyd 算法的思想)。无向图的传递闭包问题一、判断无向图中任意两个顶点之间是否有路。例1、输入一张无向图,指出该图中哪些顶点对之间有路。输入: n(顶点数, 1<= n<=20 ); e(边数, 1<= e<=210 ); 以下 e行,每行为有边连接的一对顶点。输出: k行,每行两个数,为存在路的顶点对序号 i,j ,要求 i<j 。分析: 1、采用宽度优先或深度优先遍历来解决。因为从任意一个顶点出发, 进行一次遍历,就可以求出此顶点和其它各个顶点的连通状况。所以只要把每个顶点作为出发点都进行一次遍历,就能知道任意两个顶点之间是否有路存在。一次遍历的时间复杂度为 O(n), 要穷举每个顶点,所以总的时间复杂度为 O(n*n)。无向图的传递闭包 2、设 link,longlink:array[1..20,1..20] of Boolean ;分别存放无向图和它的传递闭包。若longlink[i,j]=true ,表示顶点对 i,j 之间有路;否则无路。我们采用递推(迭代)的方法,不断对 longlink 进行运算(产生 longlink (0), longlink (1),……, longlink (n) )。对于 i,j和k=1, ……,n, 如果图中顶点 i 至顶点 j 间存在通路且通路上所有顶点的序号均属于{1,2, ……,k}, 则定义 longlink ij (k)=true ; 否则值为 false 。有: longlink ij (k)= longlink ij (k-1) or (longlink ik (k-1) and longlink kj (k-1) )。计算过程如下: longlink 的初值赋为 link ; for k:=1 to n do for i:=1 to n do for j:=1 to n do longlink[i,j]= longlink[i,j] or (longlink[i,k] and longlink[k,j]); 由于布尔型的存储量少于整数,且位逻辑运算的执行速度快于算术运算,所以空间和时间效率都很好。时间复杂度为 O(n*n*n )。了解 Floyd 算法求最短路径问题的学生,一眼就应该看出这个程序段和算法思想与 Floyd 算法是完全一致。 var link , longlink : array[1..20 , 1..20] of boolean ;{ 无向图和无向图的传递闭包。其中} 我们递推产生 longlink (0)、 longlink (1)、… longlink (n)。在递推过程中,路径长度的’+’运算和比较大小的运算用相应的逻辑运算符’ and ’和’or’代替。对于 i,j和 k=1 ‥n, 如果图中结点 i 至结点 j间存在通路且通路上所有结点的序号均属于{1‥k}, 则定义 longlink ij (k) =1 ;否则 longlink ij (k) =0 。 longlink ij (k) =longlink ij (k-1) or(longlink ik (k-1) andlonglink kj (k-1) ) 传递闭包 longlink 的计算过程如下: longlink ←link ; for k ←1 to n do { 枚举中间顶点} for i ←1 to n do{ 枚举所有顶点对} for j ←1 to n do { 计算顶点 i和顶点 j的连通情况} longlink[i ,j]←longlink[i ,j]or(longlink[i ,k]andlonglink[k ,j]) ; 无路至有路至ji ji false true ji longlink ????],[主程序 fillchar( long link ,sizeof( long link ),0); {传递闭包初始化} fillchar(link ,sizeof(link ),0);{无向图初始化} readln(n );readln(e );{读顶点数和边数} for k ←1 to e do { 输入无向图的信息} begin readln(i ,j);link[i ,j]←true ;link[j ,i]←true ; end ;{for} 计算传递闭包 longlink ; for i ←1 to n-1 do { 输出所有存在通路的顶点对} for j ←i+1 to