最小生成树

2023-01-06
作者雨辰
~5.07K 字
条评论

1. prim算法
2. kruskal算法

连通图所有生成树之中边权之和最小的生成树

使用邻接矩阵来存储图

class Graph():
    def __init__(self,n:int,maxNum = sys.maxsize,graphMatrix = []) -> None:
        if graphMatrix == []:
            self.graphMatrix = [[maxNum] * n for i in range(n)]
        else:
            self.graphMatrix = graphMatrix
        self.maxNum = maxNum
        self.size = n

    def add(self,a,b,weights):
        self.graphMatrix[a][b] = weights

    def deleat(self,a,b):
        self.graphMatrix[a][b] = self.maxNum

prim算法

从已知的点开始向外扩散，寻找最小的邻边，将顶点加入集合，已加入集合的点不能在加入，直到所有顶点加入到集合当中，构成最小生成树。

graph LR
0 --2--- 1
0 --4--- 3
1 --1--- 3
3 --5--- 2
2 --4--- 4
3 --3--- 5
1 --2--- 2
4 --8--- 5
subgraph A
0
end
subgraph B
1
2
3
4
5
end

从任意一个节点开始，将连通图划分为两个区域，一个是选中的，另一个是未选中的。每次选取选中的点当中连到未选中点的边权最小值，直到每个顶点被选中。

采用3个列表selected、minDist、parent，分别来记录：该节点是否被选中、当前节点连接顶点的边权最小值、将当前顶点连接到哪个顶点上。初始化为

.	0	1	2	3	4	5
selected	false	false	false	false	false	false
minDist	inf	inf	inf	inf	inf	inf
parent	-1	-1	-1	-1	-1	-1

接着将选中顶点的边权录入列表内

.	0	1	2	3	4	5
selected	true	false	false	false	false	false
minDist	inf	2	inf	4	inf	inf
parent	-1	0	-1	0	-1	-1

然后遍历minDis找出没选过点(即selected为false的点)最小的边(这里是1)，将他加入集合内，用selected记录，更新minDist和parent

graph LR
0 --2--- 1
0 --4--- 3
1 --1--- 3
3 --5--- 2
2 --4--- 4
3 --3--- 5
1 --2--- 2
4 --8--- 5
subgraph A
0
1
end
subgraph B
2
3
4
5
end

选中的selected更新为true,minDist更新为inf(这步可以省略)

.	0	1	2	3	4	5
selected	true	true	false	false	false	false
minDist	inf	inf	inf	4	inf	inf
parent	-1	0	-1	0	-1	-1

在将刚刚加入的点的边进行更新，如果小于当前值且未加入集合就进行赋值

.	0	1	2	3	4	5
selected	true	true	false	false	false	false
minDist	inf	inf	2	1	inf	inf
parent	-1	0	1	1	-1	-1

重复更新选点的操作直到每个点被选中。

以下是完整代码

import sys

class Graph():
    def __init__(self,n:int,maxNum = sys.maxsize,graphMatrix = []) -> None:
        if graphMatrix == []:
            self.graphMatrix = [[maxNum] * n for i in range(n)]
        else:
            self.graphMatrix = graphMatrix
        self.maxNum = maxNum
        self.size = n

    def add(self,a,b,weights):
        self.graphMatrix[a][b] = weights

    def deleat(self,a,b):
        self.graphMatrix[a][b] = self.maxNum

    def prim(self):
        selected = [False] * self.size
        minDist = [self.maxNum] * self.size
        parent = [-1] * self.size
        ans = 0

        selected[0] = True

        for i in range(self.size):
            if self.graphMatrix[0][i] != self.maxNum:
                minDist[i] = self.graphMatrix[0][i]
                parent[i] = 0

        for i in range(self.size):
            min = self.maxNum
            count = -1
            for j in range(self.size):
                if min > minDist[j] and (not selected[j]):
                    min = minDist[j]
                    count = j
            
            if count != -1:
                selected[count] = True
                ans += minDist[count]
                minDist[count] = self.maxNum

                for k in range(self.size):
                    if self.graphMatrix[count][k] < minDist[k] and (not selected[k]):
                        minDist[k] = self.graphMatrix[count][k]
                        parent[k] = count
        return ans,parent

kruskal算法

与prim算法不同，kruskal算法则是由边出发，每次选取权值最小的边

将每个边加入到列表中，按权值排好序后由小到大遍历列表，如果边所连接的两个顶点未在同一个集合，就将两个集合合并，并选取该边，这里需要用到并查集。

graph LR
subgraph A
0 --2--- 1
0 --4--- 3
1 --1--- 3
3 --5--- 2
2 --4--- 4
3 --3--- 5
1 --2--- 2
4 --8--- 5
end

列表：

权值	1	2	2	3	4	4	5	8
顶点1	4	0	1	3	0	2	3	4
顶点2	5	1	2	5	5	4	2	5

循环列表直到结束

完整代码

class DSU: #disjointed sets union
    def __init__(self,size:int):
        self.arr = list(range(size))
    
    def __findHead(self,num:int) -> int:
        if num == self.arr[num]:
            return num
        self.arr[num] = self.__findHead(self.arr[num])
        return self.arr[num]

    def merge(self,a,b) -> None:
        aHead = self.__findHead(a)
        bHead = self.__findHead(b)
        self.arr[aHead] = bHead
    
    def find(self,a,b) -> bool:
        return self.__findHead(a) == self.__findHead(b)

import sys

class Graph():
    def __init__(self,n:int,maxNum = sys.maxsize,graphMatrix = []) -> None:
        if graphMatrix == []:
            self.graphMatrix = [[maxNum] * n for i in range(n)]
        else:
            self.graphMatrix = graphMatrix
        self.maxNum = maxNum
        self.size = n

    def add(self,a,b,weights):
        self.graphMatrix[a][b] = weights

    def deleat(self,a,b):
        self.graphMatrix[a][b] = self.maxNum

    def kruskal(self):
        sideList = []
        ans = 0
        for i in range(self.size):
            for j in range(i):
                sideList.append([self.graphMatrix[i][j],i,j])
        def returnSideMap(a):
            return a[0]
        sideList.sort(key=returnSideMap)

        dsu = DSU(self.size)
        for side in sideList:
            if not dsu.find(side[1],side[2]):
                ans += side[0]
                dsu.merge(side[1],side[2])
        
        return ans

雨辰枫司的小栈

prim算法

kruskal算法