实验三:图的连通性判断
一、实验目的
用计算机语言编写图的连通性判断算法,可输入图的邻接矩阵,判断图是
否连通以及确定连通分支的个数,掌握 Warshell 算法或矩阵幂算法的实现方法。
二、实验原理
1、Warshell 算法
Warshell 算法可解决图是否连通的问题, 而且效率很高。在该算法中,矩阵
P
是判断矩阵,
p
ij
1
表示从
i
到
j
连通,
p
ij
0
表示从
i
到
j
不连通。
(1)置新矩阵 P:= C;
(2)置
i
= 1;
(3)对所有的
j
,若
p( j,i) 1
, 则对 k=1,2,…,n, 有
p( j,k) : p( j,k) p(i,k)
;
(4)
i i 1
;
(5) 如
n i
转向步骤(3), 否则停止。
2、矩阵幂算法
由于邻接阵包含了图的所有信息,和关联阵一样,是图的等价表示。可以
通过对邻接阵 C 做一些计算,得到图 G 的一些性质。例如考虑
C
中的
(i, j)
的
c
i
(
,
3
j
)
c
i,k
c
k ,l
c
l, j
(3)
c
k l
元 素
i, j
, 如 果 它 不 为 零 , 由 于 , 则 至 少 存 在 一 组
c
i,k
c
k ,l
c
l, j
1
或一个长度为 3 的链使端
i
和端
j
相连。从而,通过计算 C 的
各阶幂次可得到关于图是否连通的信息。
3
三、实验内容
1.利用 MATLAB 等语言实现图的连通性判断算法,可对输入的邻接阵进行连通
性以及连通分支数的判断。
2.比较 Warshell 算法和矩阵幂算法在算法正确性和算法复杂度上的区别。
3.对算法进行优化。
四、采用的语言
MatLab
源代码:
clear,clc;
%输入邻接矩阵
disp('图的连通性以及连通分支数的判断');
C = input('请输入图的邻接矩阵(格式如:[1 1 0;1 1 1;0 1 1]) C=');
%矩阵幂算法
n=size(C,1);%邻接矩阵阶数