无向图传递闭包.ppt

无向图的传递闭包无向图的传递闭包主要用于判断图的连通性和图中满足条件的连通分支,具有很高的实用价值。借鉴无向图的传递闭包思想,可以计算图中每一对顶点之间的最短路径(实际上就是Floyd算法的思想)。1无向图的传递闭包问题一、判断无向图中任意两个顶点之间是否有路。例1、输入一张无向图,指出该图中哪些顶点对之间有路。输入:n(顶点数,1<=n<=20);e(边数,1<=e<=210);以下e行,每行为有边连接的一对顶点。输出:k行,每行两个数,为存在路的顶点对序号i,j,要求i<j。分析:1、采用宽度优先或深度优先遍历来解决。因为从任意一个顶点出发,进行一次遍历,就可以求出此顶点和其它各个顶点的连通状况。所以只要把每个顶点作为出发点都进行一次遍历,就能知道任意两个顶点之间是否有路存在。一次遍历的时间复杂度为O(n),要穷举每个顶点,所以总的时间复杂度为O(n*n)。2无向图的传递闭包 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},则定义longlinkij(k)=true;否则值为false。有:longlinkij(k)= longlinkij(k-1) or (longlinkik(k-1) and longlinkkj(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算法是完全一致。3var 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},则定义longlinkij(k)=1;否则longlinkij(k)=0。longlinkij(k)=longlinkij(k-1)or(longlinkik(k-1)andlonglinkkj(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]);无路至有路至jijifalsetruejilonglink????],[4主程序fillchar(longlink,sizeof(longlink),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 n do if longlink[i,j] then 输出i和j;5无向图的传递闭包问题二、寻找满足条件的连通分支。例2、输入一张顶点带权的无向图,分别计算含顶点数最多的一个连通分支和顶点的权之和最大的一个连通分支。输入:n(顶点数,1<=n<=20);以下n行,依次表示顶点1 ~ 顶点n上的权;e(边数,1<=e<=210);以下e行,每行为有边连接的一