一种判定的无向图连通性的快速Warshall算法

【摘 要】基于判断图是否连通的Warshall算法，提出和证明了一种新的判断无向图的连通性的算法，该新算法与Warshall算法相比，时间复杂度仅仅是Warshall算法的四分之一，空间复杂度是Warshall算法的二分之一，并且易于在计算机上实现，并把这种新的算法命名为判断无向图连通性的快速Warshall算法。

【关键词】邻接矩阵；Warshall算法；连通性

引 言

在实际中判断一个图是否连通是一个很重要的问题，例如计算网络的最小点割集、网络可靠性问题，计算网络的连通度.对于大规模的网络图而言，通过定义去判断一个图是否是连通的已经不可能.随着现代计算机技术的发展，判断图的连通性一般是把一个网络图转化为邻接矩阵，设计相关的判断方法，最后在计算机中实现。用计算机在判断一个图是否是连通的有很多的方法，比较经典的基于邻接矩阵的Warshall 算法，当节点数目很变得很大时候，空间复杂度和时间复杂度变得很高，甚至超出计算机的内存，因此设计出效率更高的算法有着重要的意义。整个文章的结构安排是：第一部分介绍相关的概念引理，第二部分介绍算法的理论基础，第三部分是新算法的设计，第四部分是新算法与Warshall 算法的时间复杂度和空间复杂度的比较。

1、基本的概念和引理

（1）连通性概念

图中两点的连通：如果在图G 中u， v两点有路相通，则称顶点u， v在图G 中连通；如果图G 中任二顶点都连通，则图G 称为连通图。

（2）图的邻接矩阵

设G = （V ， E）是具有n 个顶点的图，则G 的邻接矩阵ij n n A G a ? （ ） = （ ）是具有如下性质的阶方阵：

（3）判断图是否连通的Warshall算法

引理1（Warshall算法）设A是图G（V， E）的邻接矩阵，对于矩阵

如果矩阵S中的元素全部为非零元素，那么图G 是连

通图，否则图G 是非连通图，其中 { ， ， } 1 2 n V = v v Kv .

2、新算法的理论基础

在实际中判断一个图是否连通是一个很重要的问题，例如计算网络的最小点割集、网络可靠性问题。对于大规模的网络图而言，通过定义去判断一个图是否是连通已经不可能。随着现代计算机技术的发展，判断图的连通性一般是把一个网络图转化为邻接矩阵，设计相关的判断方法，最后在计算机中实现。 Warshall 算法就是其中的一种重要的方法。但是随着节点数目的增加判断图连通性的Warshall 算法的空间复杂度和时间复杂度也逐渐加

大。考虑到无向图的邻接矩阵是对称的，并且邻接矩阵的副上三角元素已经包含的图中每个点之间的相互关系，结合Warshall 算法的思想和邻接矩阵的副上三角元素的关系设计出一种快速判断一个无向图是否是连通的一种算法。根据上面的讨论可以得到定理：定理1 设矩阵

ij n n A a ? = （ ） 是无向图G（V ， E）的邻接矩阵，

ij n n B b ? = （ ）

是矩阵A的副上三角矩阵，如果?-

ij c 为零表示不存在这样的路径。由此可

知如果S 'ij非零，则

i v 可达j v ………………………………………（1）

现在考虑C的副上三角矩阵

的副上三角元素非零，即所有的S 0，（i j）（i， j 1，2， m） ij > < = K 根据（1）知

可达

j v ，遍历副上三角的所有元素以及无向图邻接矩阵的的对称性可得，图

G 是连通的.反之如果

i v 可达

j v ，则有

S 0，（i j）（i， j 1，2， m） ij > < = K ……………………………………证毕。

3、新算法设计

现在根据定理1 来设计一个判断无向图是否连通的新算法，步骤如下：

步骤1：输入图G 的邻接矩阵

ij n n A a ? = （ ） ；

步骤2：计算出A的副上三角矩阵

步骤4： S的所有副上三角元素非零，则图G 是连通的，输出1，否则是非连通的，输出0；将上述的算法命名为：判断无向图连通性的快速Warshall 算法。注：在编制计算机程序时，步骤3 中所有的非副上三角元素将不参与矩阵的相关运算。

算法流程图见（图一）

4、两种算法的时间复杂度与空间复杂度的比较

（1）时间复杂度的比较

现在假设邻接矩阵是A 的阶数是n ，Warshall 算法是对邻接矩阵进

行矩阵乘法的运算，根据相关的数学知识，需要做乘法运算的次是：

g（n） = （n -1）（n - 2）n3 / 2………………………………………………（2）

以及做加法的次数是： n2 （n -1）2 （n - 2） / 2 .

而新算法做乘法的次数是：

从式（4）中不难发现改进后的算法的的效率较原算法效率更高，时间

复杂度更低，效率大约是原来的4 倍。

（2）空间复杂度的比较

从计算机内存存放矩阵的角度来看，判断图连通性的快速Warshall 算法只需要存储有用数据，即矩阵的副上三角元素.较Warshall 算法存储的空间减少了一半以上.

5、结论

从上面的分析可以看出改进后的方法速度更快，计算时占用的内存更少！更符合大规模的运算，从而在计算网络的连通度以及系统网络可靠性方面更加快捷.

【参考文献】

[1]卢开澄，卢华明.论及其应用[M].北京：清华大学出版社，1998：17.

[2]耿素云，屈婉玲，张立昂.离散数学[M].北京：清华大学出版社，2005：88-92.

[3]刘晓利，秦奋涛.有向图的强连通性分析及判别算法[J].计算机应用与软

件，2005，22（4）：138-139.