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

吴海洋

摘 要：本文基于判断图是否连通的Warshall算法，提出和证明了一种新的判断无向图的连通性的算法.

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

中图分类号：G642 文献标识码：B 文章编号：1002-7661（2015）13-011-01

一、新算法的理论基础

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

定理1设矩阵 是无向图 的邻接矩阵， 是矩阵A的副上三角矩阵，如果 的副上三角元素都是非零的，那么图 是连通的，否则是非连通的，其中n是图G节点数目.

证明：由（引理1）知：图 连通的充分必要条件是矩阵 中的所有的元素非零，其中C是图 的邻接矩阵.计 ，其中 . 的值表示从节点 出发经过 步到达 的路径数目。如果 为零表示不存在这样的路径。由此可知如果 非零，则 可达

1、现在考虑C的副上三角矩阵 ，如果 的副上三角元素非零，即所有的 根据（1）知 可达 ，.遍历副上三角的所有元素以及无向图邻接矩阵的的对称性可得，图G是连通的.反之如果 可达 ，则有 证毕.

二、新算法设计

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

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

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

步骤3：计算出 的副上三角元素；

步骤4：S的所有副上三角元素非零，则图G是连通的，输出1，否则是非连通的，输出0；

将上述的算法命名为：判断无向图连通性的快速Warshall算法.

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

1、时间复杂度的比较

现在假设邻接矩阵是 的阶数是 ，Warshall算法是对邻接矩阵进行矩阵乘法的运算，根据相关的数学知识，需要做乘法运算的次是：

…..（2）

以及做加法的次数是： .

而新算法做乘法的次数 .（3）

现在对式（2）和式（3）做比值并取极限 ……………（4）

从式（4）中不难发现改进后的算法的的效率较原算法效率更高，时间复杂度更低，效率大约是原来的4倍。

2、空间复杂度的比较

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

四、结论

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

参考文献：

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