Python描述数据结构之最小生成树篇!零基础必学!
前言
本篇章主要介绍图的最小生成树,包括Prim算法和Kruskal算法,并用Python代码实现。
1. 创建图
在开始之前,我们先创建一个图,使用邻接矩阵表示图:
class Graph(object): """ 以邻接矩阵为存储结构创建无向网 """ def __init__(self, kind): # 图的类型: 无向图, 有向图, 无向网, 有向网 # kind: Undigraph, Digraph, Undinetwork, Dinetwork, self.kind = kind # 顶点表 self.vertexs = [] # 边表, 即邻接矩阵, 是个二维的 self.arcs = [] # 当前顶点数 self.vexnum = 0 # 当前边(弧)数 self.arcnum = 0 def CreateGraph(self, vertex_list, edge_list): """ 创建图 :param vertex_list: 顶点列表 :param edge_list: 边列表 :return: """ self.vexnum = len(vertex_list) self.arcnum = len(edge_list) for vertex in vertex_list: vertex = Vertex(vertex) # 顶点列表 self.vertexs.append(vertex) # 邻接矩阵, 初始化为无穷 self.arcs.append([float('inf')] * self.vexnum) for edge in edge_list: ivertex = self.LocateVertex(edge[0]) jvertex = self.LocateVertex(edge[1]) weight = edge[2] self.InsertArc(ivertex, jvertex, weight) def LocateVertex(self, vertex): """ 定位顶点在邻接表中的位置 :param vertex: :return: """ index = 0 while index < self.vexnum: if self.vertexs[index].data == vertex: return index else: index += 1 def InsertArc(self, ivertex, jvertex, weight): """ 创建邻接矩阵 :param ivertex: :param jvertex: :param weight: :return: """ if self.kind == 'Undinetwork': self.arcs[ivertex][jvertex] = weight self.arcs[jvertex][ivertex] = weight
2. 问题来源
假设要在n nn个城市之间建立通信联络网,则连通n nn个城市只需要n − 1 n-1n−1条线路。在每两个城市之间都可以建立一条线路,相应地都要付出一定的经济代价,n nn个城市之间最多可以建立n ( n − 1 ) 2 \frac {n(n-1)} {2}2n(n−1)条线路。这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个连通网,即如何在这些可能的线路中选择n − 1 n-1n−1条,以使花费的经费最少。
我们可以用连通网来表示n nn个城市以及n nn个城市间可能建立的通信线路,其中顶点可以表示城市,边可以表示两个城市之间的通信线路,边的权值就是修建这条线路所需的经费。对于n nn个顶点的连通网可以建立许多不同的生成树,每一棵树都可以是一个连通网,现在要从中选择出一棵使用经费最少的生成树。这个问题就是构造连通网的最小代价生成树( M i n i m u m (Minimum(Minimum C o s t CostCost S p a n n i n g SpanningSpanning T r e e ) Tree)Tree)的问题,简称最小生成树( M S T ) (MST)(MST)问题。
MST的性质:假设N = ( V , { E } ) N=(V,\{E\})N=(V,{E})是一个连通网,U UU是顶点集V VV的一个非空子集。若( u , v ) (u,v)(u,v)是一条具有最小权值的边,其中u ∈ U , v ∈ V − U u\in U,v\in V-Uu∈U,v∈V−U,则必存在一棵包含边( u , v ) (u,v)(u,v)的最小生成树。
P r i m PrimPrim算法和K r u s k a l KruskalKruskal算法是两个利用MST性质构造最小生成树的经典算法。
3. Prim算法
P r i m PrimPrim算法,中文名叫普里姆算法。基本思想如下:
(1) 指定连通网N NN中的某一顶点作为构造最小生成树的起点,并令U = { w } , T E = { } U=\{w\},TE=\{\}U={w},TE={};
(2) 在所有u ∈ U 、 v ∈ V − U u\in U、v\in V-Uu∈U、v∈V−U的边中,找到一条权值最小的边( u , v ) ∈ E (u,v)\in E(u,v)∈E,将u uu并入到U UU中,并将边( u , v ) (u,v)(u,v)并入到T E TETE中;
(3) 重复执行第二步,直到U = V U=VU=V,此时最小生成树包含n − 1 n-1n−1条边。
这里使用一个辅助数组closedge,用来存储从U UU到U − V U-VU−V中权值最小的边及顶点U UU的下标,除此之外还需要一个列表arc来存储最小生成树的边。下面结合着P r i m PrimPrim算法来分析一下上面的那个无向网:
(1) P r i m PrimPrim算法一直在更新两个集合,即已访问顶点集合U UU和未访问顶点集合U − V U-VU−V,然后从这两个集合组成的边中选择权值最小的边。这里以顶点A AA为起始点,先将它加入U UU中,即其对应的closedge置为[ ( 0 , 0 ) ] [(0,0)][(0,0)]。此时U UU中只有顶点A AA,与A AA相连的边有A B ABAB、A C ACAC和A D ADAD,初始closedge为[ ( 0 , 0 ) , ( 0 , 6 ) , ( 0 , 1 ) , ( 0 , 5 ) , ( 0 , ∞ ) , ( 0 , ∞ ) ] [(0,0),(0,6),(0,1),(0,5),(0,\infty),(0,\infty)][(0,0),(0,6),(0,1),(0,5),(0,∞),(0,∞)],其中权值最小的边的另一个顶点索引为2,即顶点C CC,然后根据这个索引2确定了该边对应两个顶点的索引( 0 , 2 ) (0,2)(0,2),即边A C ACAC,图中的红色线表示,将该边加入到列表arc中,同时将C CC加入U UU中,即将其对应的closedge由( 0 , 1 ) (0,1)(0,1)置为( 0 , 0 ) (0,0)(0,0),此时closedge为[ ( 0 , 0 ) , ( 0 , 6 ) , ( 0 , 0 ) , ( 0 , 5 ) , ( 0 , ∞ ) , ( 0 , ∞ ) ] [(0,0),(0,6),(0,0),(0,5),(0,\infty),(0,\infty)][(0,0),(0,6),(0,0),(0,5),(0,∞),(0,∞)];
(2) 此时U UU中有顶点A AA和C CC,然后去找两顶点集合对应权值最小的边,与C CC相连的边有C A CACA、C B CBCB、C D CDCD、C E CECE和C F CFCF,更新closedge为[ ( 0 , 0 ) , ( 2 , 5 ) , ( 0 , 0 ) , ( 0 , 5 ) , ( 2 , 6 ) , ( 2 , 4 ) ] [(0,0),(2,5),(0,0),(0,5),(2,6),(2,4)][(0,0),(2,5),(0,0),(0,5),(2,6),(2,4)],更新的原则是如果新边的权重比closedge中的小,更新,否则不更新,其中权值最小的边的另一个顶点索引为5,即顶点F FF,然后根据这个索引5确定了该边对应两个顶点的索引( 2 , 5 ) (2,5)(2,5),即边C F CFCF,图中的橙色线表示,将该边加入到列表arc中,同时将F FF加入U UU中,即将其对应的closedge由( 2 , 4 ) (2,4)(2,4)置为( 2 , 0 ) (2,0)(2,0),此时closedge为[ ( 0 , 0 ) , ( 2 , 5 ) , ( 0 , 0 ) , ( 0 , 5 ) , ( 2 , 6 ) , ( 2 , 0 ) ] [(0,0),(2,5),(0,0),(0,5),(2,6),(2,0)][(0,0),(2,5),(0,0),(0,5),(2,6),(2,0)];
(3) 此时U UU中有顶点A AA、C CC和F FF,然后去找两顶点集合对应权值最小的边,与F FF相连的边有F C FCFC、F D FDFD和F E FEFE,更新closedge为[ ( 0 , 0 ) , ( 2 , 5 ) , ( 0 , 0 ) , ( 5 , 2 ) , ( 2 , 6 ) , ( 2 , 0 ) ] [(0,0),(2,5),(0,0),(5,2),(2,6),(2,0)][(0,0),(2,5),(0,0),(5,2),(2,6),(2,0)],其中权值最小的边的另一个顶点索引为3,即顶点D DD,然后根据这个索引3确定了该边对应两个顶点的索引( 5 , 2 ) (5,2)(5,2),即边F D FDFD,图中的黄色线表示,将该边加入到列表arc中,同时将D DD加入U UU中,即将其对应的closedge由( 5 , 2 ) (5,2)(5,2)置为( 5 , 0 ) (5,0)(5,0),此时closedge为[ ( 0 , 0 ) , ( 2 , 5 ) , ( 0 , 0 ) , ( 5 , 0 ) , ( 2 , 6 ) , ( 2 , 0 ) ] [(0,0),(2,5),(0,0),(5,0),(2,6),(2,0)][(0,0),(2,5),(0,0),(5,0),(2,6),(2,0)];
(4) 此时U UU中有顶点A AA、C CC、F FF和D DD,然后去找两顶点集合对应权值最小的边,与D DD相连的边有D A DADA、D C DCDC和D F DFDF,更新closedge为[ ( 0 , 0 ) , ( 2 , 5 ) , ( 0 , 0 ) , ( 5 , 0 ) , ( 2 , 6 ) , ( 2 , 0 ) ] [(0,0),(2,5),(0,0),(5,0),(2,6),(2,0)][(0,0),(2,5),(0,0),(5,0),(2,6),(2,0)],其中权值最小的边的另一个顶点索引为1,即顶点B BB,然后根据这个索引1确定了该边对应两个顶点的索引( 2 , 1 ) (2,1)(2,1),即边C B CBCB,图中的绿色线表示,将该边加入到列表arc中,同时将B BB加入U UU中,,即将其对应的closedge由( 2 , 5 ) (2,5)(2,5)置为( 2 , 0 ) (2,0)(2,0),此时closedge为[ ( 0 , 0 ) , ( 2 , 0 ) , ( 0 , 0 ) , ( 5 , 0 ) , ( 2 , 6 ) , ( 2 , 0 ) ] [(0,0),(2,0),(0,0),(5,0),(2,6),(2,0)][(0,0),(2,0),(0,0),(5,0),(2,6),(2,0)];
(5) 此时U UU中有顶点A AA、C CC、F FF、D DD和B BB,然后去找两顶点集合对应权值最小的边,与B BB相连的边有B A BABA、B C BCBC和B E BEBE,更新closedge为[ ( 0 , 0 ) , ( 2 , 0 ) , ( 0 , 0 ) , ( 5 , 0 ) , ( 1 , 3 ) , ( 2 , 0 ) ] [(0,0),(2,0),(0,0),(5,0),(1,3),(2,0)][(0,0),(2,0),(0,0),(5,0),(1,3),(2,0)],其中权值最小的边的另一个顶点索引为4,即顶点E EE,然后根据这个索引4确定了该边对应两个顶点的索引( 1 , 4 ) (1,4)(1,4),即边B E BEBE,图中的蓝色线表示,将该边加入到列表arc中,同时将E EE加入U UU中,,即将其对应的closedge由( 2 , 6 ) (2,6)(2,6)置为( 1 , 3 ) (1,3)(1,3),此时closedge为[ ( 0 , 0 ) , ( 2 , 0 ) , ( 0 , 0 ) , ( 5 , 0 ) , ( 1 , 0 ) , ( 2 , 0 ) ] [(0,0),(2,0),(0,0),(5,0),(1,0),(2,0)][(0,0),(2,0),(0,0),(5,0),(1,0),(2,0)];
至此,未访问顶点的集合已为空,顶点已全部被访问,最小生成树为:{ ( A , C ) , ( C , F ) , ( F , D ) , ( C , B ) , ( B , E ) } \{(A,C),(C,F),(F,D),(C,B),(B,E)\}{(A,C),(C,F),(F,D),(C,B),(B,E)}。
P r i m PrimPrim算法实现如下:
def GetMin(self, closedge): """ 找到当前closedge中权值最小的边 :param closedge: :return: """ index = 0 vertex = 0 minweight = float('inf') while index < self.vexnum: if closedge[index][1] != 0 and closedge[index][1] < minweight: minweight = closedge[index][1] vertex = index index += 1 return vertex def Prim(self, start_vertex): k = self.LocateVertex(start_vertex) closedge = [] arc = [] for index in range(self.vexnum): # 下标权值, 初始化 closedge.append([k, self.arcs[k][index]]) # 将起始点加入到U中 closedge[k][1] = 0 index = 1 while index < self.vexnum: # 找到了与下标为k相连的最小边 minedge = self.GetMin(closedge) # 将当前最小权值的边加入到最小生成树arc arc.append([self.vertexs[closedge[minedge][0]].data, self.vertexs[minedge].data, closedge[minedge][1]]) # 将最小边权值置为0, 即将顶点v加入U中, 表示该顶点已经在最小生成树内 closedge[minedge][1] = 0 i = 0 # 重新选择权值最小边 while i < self.vexnum: if self.arcs[minedge][i] < closedge[i][1]: # 更新 最小边的权值及下标 closedge[i] = [minedge, self.arcs[minedge][i]] i += 1 index += 1 return arc
可以看到P r i m PrimPrim算法的时间复杂度与图中顶点的数目有个很大关系,所以它更适合稠密网求最小生成树。
4. Kruskal算法
K r u s k a l KruskalKruskal算法,中文名叫克鲁斯卡尔算法。基本思想如下:
(1) 将连通网N NN中的所有边存入集合Edges,并按权值从小到大进行排列,同时令U = V , T E = { } U=V,TE=\{\}U=V,TE={},T E TETE是N NN上最小生成树中边的集合,此时为空,即最小生成树T TT中的每一个顶点都自带一个连通分量;
(2) 依次访问Edges中的边,若当前被访问的边的两个顶点属于不同的连通分量,即不构成环,则将该边加入到T E TETE中,并标记当前两个顶点所在的连通分量为同一个连通分量;否则将该边从Edges中删除;
(3) 重复执行第二步,直到最小生成树T TT的所有顶点均属于同一连通分量,此时E d g e s EdgesEdges中的边与组成最小生成树T TT的边相同,这些边组成了集合T E TETE。
这里使用一个辅助数组flags来记录每个顶点所属的连通分量的序号。下面结合着K r u s k a l KruskalKruskal算法来分析一下上面的那个无向网:
(1) K r u s k a l KruskalKruskal算法在不断遍历列表edges中的每一条边并更新列表edges。首先遍历第一条边( A , C ) (A,C)(A,C),图中的红色线,发现这条边的两个顶点属于不同的连通分量,然后就更新辅助数组flags中对应顶点的序号,让它们俩的序号一致;
(2) 然后遍历下一条边( D , F ) (D,F)(D,F),图中的橙色线,发现这条边的两个顶点属于不同的连通分量,然后就更新辅助数组flags中对应顶点的序号,让它们俩的序号一致;
(3) 然后遍历下一条边( B , E ) (B,E)(B,E),图中的黄色线,发现这条边的两个顶点属于不同的连通分量,然后就更新辅助数组flags中对应顶点的序号,让它们俩的序号一致;
(4) 然后遍历下一条边( C , F ) (C,F)(C,F),图中的绿色线,发现这条边的两个顶点属于不同的连通分量,然后就更新辅助数组flags中对应顶点的序号,让它们俩的序号一致;
(5) 然后遍历下一条边( A , D ) (A,D)(A,D),发现这条边的两个顶点属于相同的连通分量,即加入这条边后,无向网就会产生回路,删除列表edges中的这条边;
(6) 然后遍历下一条边( B , C ) (B,C)(B,C),图中的蓝色线,发现这条边的两个顶点属于不同的连通分量,然后就更新辅助数组flags中对应顶点的序号,让它们俩的序号一致;
(7) 然后遍历下一条边( C , D ) (C,D)(C,D),发现这条边的两个顶点属于相同的连通分量,即加入这条边后,无向网就会产生回路,删除列表edges中的这条边;
然后继续遍历,直至遍历完列表edges,列表edges中剩余的边就构成了最小生成树,最小生成树为:{ ( A , C ) , ( D , F ) , ( B , E ) , ( C , F ) , ( B , C ) } \{(A,C),(D,F),(B,E),(C,F),(B,C)\}{(A,C),(D,F),(B,E),(C,F),(B,C)}。
K r u s k a l KruskalKruskal算法实现如下:
def AddEdges(self): """ 将连通网中的边加入到列表AddEdges中 :return: """ edges = [] i = 0 while i < self.vexnum: j = 0 while j < self.vexnum: if self.arcs[i][j] != float('inf'): edges.append([self.vertexs[i].data, self.vertexs[j].data, self.arcs[i][j]]) j += 1 i += 1 # 按权重从小到大进行排序 return sorted(edges, key=lambda item: item[2]) def Kruskal(self): edges = self.AddEdges() flags = [] for index in range(self.vexnum): flags.append(index) index = 0 while index < len(edges): ivertex = self.LocateVertex(edges[index][0]) jvertex = self.LocateVertex(edges[index][1]) if flags[ivertex] != flags[jvertex]: # 两个顶点不属于同一连通分量 # 找到它们各自的连通分量的序号 iflag = flags[ivertex] jflag = flags[jvertex] # 它们两个如何合并, 找找flags有没有与之相同的 limit = 0 while limit < self.vexnum: if flags[limit] == jflag: # 将j和i的连通序号设置相同, 表示它俩是连通的 flags[limit] = iflag limit += 1 # index就要放这里, 因为删除边后edges长度就会减少1 index += 1 else: # 已经连通了, 即加入这条边就构成了环 # 删除这条边 edges.pop(index) return edges
可以看到K r u s k a l KruskalKruskal算法的时间复杂度与图中边的数目有个很大关系,所以它更适合稀疏网求最小生成树。
5. 代码测试
测试代码如下:
if __name__ == '__main__': graph = Graph(kind='Undinetwork') graph.CreateGraph(vertex_list=['A', 'B', 'C', 'D', 'E', 'F'], edge_list=[('A', 'B', 6), ('A', 'C', 1), ('A', 'D', 5), ('B', 'C', 5), ('B', 'E', 3), ('C', 'D', 5), ('C', 'E', 6), ('C', 'F', 4), ('D', 'F', 2), ('E', 'F', 6)]) # 起始位置的index为0 mst1 = graph.Prim('A') print('Prim最小生成树为: ') for edge in mst1: print('{0}-->{1}: {2}'.format(edge[0], edge[1], edge[2])) mst2 = graph.Kruskal() print('Kruskal最小生成树为: ') for edge in mst2: print('{0}-->{1}: {2}'.format(edge[0], edge[1], edge[2]))
测试结果如下:
你学会了吗?
此文转载文,著作权归作者所有,如有侵权联系小编删除
原文地址:https://blog.****.net/qq_42730750/article/details