求最大生成树的改进的矩阵算法

2020-02-02张亚蕾

渤海大学学报（自然科学版） 2020年4期

张亚蕾

（仰恩大学数学系，福建泉州 362014）

0 引言

树是图论中很重要的概念，最早是由德国物理学家基尔霍夫提出来的，当时没有引起人们的重视，但是现在树已经发展为图论中重要部分，在大数据、人工智能、物流运输、道路工程、管道问题等许多领域和实际问题中都有着广泛的应用.所谓树就是连通且没有回路的无向图，生成树就是一个无向连通图中连通且没有回路的生成子图，带权无向连通图的最小生成树问题作为一个典型的图论问题，求最小生成树算法和求生成树的权这些问题已经比较成熟，常用的求最小生成树算法有克鲁斯卡尔算法和普里姆算法［1-2］，除此外还有破圈法、逐步短接法［1］、Sollin算法、Dijkstra算法等算法，近年来最小生成树算法的应用也越来越多［3-4］.毛华等［5］研究了求最小生成树的矩阵算法，刘育刚［6］对最小生成树的邻接矩阵法也进行了研究，本文在毛华等人研究的基础上讨论最大生成树的改进的权矩阵算法及其应用.本文中的G=V,E,W表示无向图，其中V={ }v1,v2,…,vn为无向图的顶点集，E为该无向图的边集，W为该无向图中边的权集，(vi,vj)表示以vi,vj为顶点的边，Wij为边的(vi,vj)权.

1 预备知识

无向树的定义［1-2］：一个连通且无回路的无向图称为树，也称为自由树.

最大生成树的定义［1-2］：设G=V,E是一个具有n个结点的无向连通图，包含G所有n个结点，保持连通性的权的极大连通子图就称为G的最大生成树.

生成树存在定理［1-2］：一个无向图带权连通图一定存在生成树.假设G=V,E,W是一个无向连通图，U是顶点集V的一个非空子集.若(u ,v)是一条权最大边，其中u∈U，v∈V-U，则一定可以找到一棵的最大生成树，这个最大生成树包含边(u ,v).

2 三种常见的最大生成树算法

2.1 利用Kruskal算法求最大生成树

Kruskal算法也称为闭圈法，该算法最早由Kruskal于1956年提出，最大生成树的Kruskal算法的基本思想：首先按照边的权值由大到小把所有边排序，然后依次选取没有进入生成树中权值最大的边e，如果没有构成回路，则将该边加入生成树T中，重复此过程至生成树中达到n-1条边为止.这时我们发现T中不含任何回路且连通，因此是树，而且按照这种过程得到的一定是最大生成树[7].

2.2 利用破圈法求最大生成树

我国的管梅谷教授于1975年提出了计算最小生成树的破圈法.破圈法是“见圈破圈”的一种算法：即如果看到无向连通图中有一个回路，就将这个回路中的边去掉一条，直至图中再无任何回路且还保持连通性为止.利用破圈法求最大生成树，就是见圈就删除该回路中权最小的那个边，如此见圈破圈，直到图中没有一圈为止，这是剩下的图一定是原图（原图是无向连通图）的最大生成树[7].

2.3 利用Prim算法求最大生成树

Prim算法虽然是以美国计算机科学家罗伯特·普里姆命名的，但是最早是在1930年由捷克数学家沃伊捷赫·亚尔尼克发现；因此，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法.最大生成树Prim算法是按逐个将顶点连通的方式来构造的.首先任意选取图G=V，E，W中的一个顶点v加入到顶点集Q中，之后在V-Q中任选顶点u，如果u到集合Q中的某个顶点有边，并且该边的权是所有连接Q中的点和不在Q中的点的边中权最大的，就将顶点u加入集合Q中，同时将刚才找到的那个权最大边加入边集ET中，如此反复重复该过程，直到原图中的所有顶点都进入Q中，这时候ET中的边和所有顶点就可以形成原图的一棵最大生成树[7].

3 改进的邻接矩阵求最大生成树

定义1［1］：设图G是一个无向图，令aij为vi邻接到vj的边的条数，则称()aijn×n为G的邻接矩阵.

定义2：设图G是一个无向连通简单图，Wij为边( )vi,vj的权，仿照邻接矩阵定义给出权矩阵A的定义如下：

定义3：设图G是一个无向连通复杂图，Wij为边( )vi,vj的权，这是可能会有平行边，定义改进的权矩阵A如下：

3.1 改进的邻接矩阵算法

毛华等介绍了求最小生成树的权矩阵算法［5］，我们仿照该算法给出最大生成树的矩阵算法.假设G=是一个具有n个顶点的带权无向连通图，A表示其权矩阵，定义如上定义2和定义3.

3.2 最大生成树的权矩阵算法

假设G=V,E,W是一个具有n个顶点的带权无向连通图，开始时，我们设Q=∅，ET=∅，K=0，然后在权矩阵任取一行找出一个最大元素，不妨设为aij，若边，此时用*在权矩阵中标注元素aij，aji；若边(ui,uj) ⊂ ET，则令ET=ET，Q=Q，K=K，此时用×在权矩阵中标注元素aij，aji.然后在权矩阵中选取Q中元素对应行中除了标注外的最大元素，重复上述过程，直至K=n-1，算法结束，此时ET中的元素对应的边的导出子图就是图G的一个最大生成树.

3.3 最大生成树的改进的权矩阵算法

假设G=V,E,W是一个具有n个顶点的带权无向连通图，显然G的权矩阵是一个对称矩阵，因此我们只需要从主对角线以上（或以下）找最大元素即可.开始时，我们设Q=∅，ET=∅，K=0，然后在权矩阵主对角线以上（或以下）的任取一列（或者一行）找出一个最大元素，不妨设为aij，若边(ui,uj) ⊄ET，则令，此时用*在权矩阵中标注元素aij，若边(ui,uj) ⊂ET，则令ET=ET，Q=Q，K=K，此时用×在权矩阵中标注元素aij.然后在权矩阵中主对角线以上（或以下）选取Q中元素对应列（或者行）中除了标注外的最大元素，重复上述过程，直至K=n-1，算法结束，此时ET中的元素对应的边的导出子图就是图G的一个最大生成树.

3.4 改进的权矩阵法的具体步骤

（1）初始状态，ET为空集，Q= ∅，ET= ∅，K=0；

（2）在权矩阵主对角线元素以上（或以下）的任取一列（或者一行）找出一个最大元素，不妨设为aij，若此时用*在权矩阵中标注元素aij，若边此时用×在权矩阵中标注元素aij.若K=n-1，算法结束，此时ET中的元素对应的边的导出子图就是图G的一个最大生成树.若K＜n-1，转（3）.

（3）在权矩阵主对角线以上（或以下）选取Q中元素对应列（或者行）中除了标注外的最大元素，转（2）.

3.5 算法分析

Kruskal算法的时间复杂度不仅与无向连通图的边的数目有关，还与顶点的个数有关，其时间复杂度为O（mlnn），破圈法则只与图中边的个数有关，时间复杂度为O（mlnm），当G中圈较少时，这两种算法用破圈法比较好.Prim算法的计算复杂度和图的边树无关，只和顶点的数目有关，其复杂度为O（n2），Prim算法和Kruskal算法分别适用于稠密图和稀疏图，但两种算法都不能根据图的顶点数、顶点的度数以及边的分布情况自适应地改变自身.参考文献［5］中毛华提出的权矩阵算法考虑整个的时间复杂度为O（n3），我们今天改进了权矩阵算法，其复杂度为权矩阵算法的一半.