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