无向图的最小生成树 (MST) 是一棵树，使得树的所有边权重之和最小。 有两种实现 MST 的方法，即 Kruskal 和 Prim 算法。

Kruskal 算法

脚步

• 将图的所有边从低权重排序到高权重。
• 如果添加这条边不会在图中创建循环，则取最低权重的边并将其添加到生成树中。 我们使用不相交集来检测循环。

• 重复此过程，直到所有顶点都被边缘覆盖。

代码实现

class DisjointSet:
    parent = {}
 
    def makeSet(self, n):
        for i in range(n):
            self.parent[i] = i
 
    def find(self, k):
        # if `k` is root
        if self.parent[k] == k:
            return k
        return self.find(self.parent[k])
 
    def union(self, a, b):
        x = self.find(a)
        y = self.find(b)
        self.parent[x] = ydef kurskals_algo(A, B):
    mst = []
    ds = DisjointSet()
    ds.makeSet(A)    index = 0
    B.sort(key=lambda x: x[2])    while len(mst) != A - 1:
        (src, dest, weight) = B[index]
        index = index + 1        x = ds.find(src-1)
        y = ds.find(dest-1)        if x != y:
            mst.append((src, dest, weight))
            ds.union(x, y)
    
    cost = sum([x[2] for x in mst])return cost

Kruskal 的算法专注于边缘。 在每次迭代中处理 1 条边。 Kruskal 算法的时间复杂度为 O(ElogV)

应用

• 电缆敷设
• 电视网络位置
• 行程安排
• 局域网

Prim 算法

脚步

• 用随机选择的顶点初始化最小生成树。
• 找到将树连接到新顶点的所有边，找到最小值并将其添加到树中
• 继续重复步骤 2，直到我们得到最小生成树

代码实现

from collections import defaultdict
import math
 
class Graph:
    def __init__(self, N):
        self.V = N
        self.edges = {}    def addEdge(self, s, d, w):
        if (s-1, d-1) in self.edges:
            self.edges[(s-1, d-1)] = min(self.edges[(s-1, d-1)], w)
        else:
            self.edges[(s-1, d-1)] = w
    
    def prims_algo(self):
        visited = [0]*self.V
        processed = set()
        mst = []
        cost = 0        from heapq import heappush, heappop
        q = []        min_cost = math.inf
        for (s, d), w in self.edges.items():
            if min_cost > w:
                min_cost = w
                i_s, i_d = s, d
        heappush(q, (min_cost, i_s, i_d))        while len(mst) < self.V-1 and q:
            w, s, d = heappop(q)
            if (visited[s] + visited[d]) < 2:
                visited[d] = 1
                visited[s] = 1
                cost += w 
                mst.append([s, d, w])
                processed.discard((s, d))
            
                for edge, w in self.edges.items() :
                    if (s in edge) or (d in edge):
                        if (visited[edge[0]] + visited[edge[1]]) < 2 and (edge[0], edge[1]) not in processed:
                            heappush(q, (w, edge[0], edge[1]))
                            processed.add((edge[0], edge[1]))
            
        return mst, costif __name__=='__main__':
    A = 5
    B = [[1, 2, 3],[2, 3, 4],[3, 4, 5],[4, 5, 6],[5, 1, 2],[2, 4, 3],[2, 5, 5],[1, 3, 2]]    g = Graph(A)
    for s, d, w in B:
        if s!=d:
            if s > d:
                s, d = d, s
            g.addEdge(s, d, w)print(g.prims_algo())

Prim 的算法专注于顶点。 在每次迭代中处理 1 个顶点。 Prim 算法的时间复杂度为 O(ElogV) 。

应用

• 聚类分析
• 旅行商问题
• 铁路和公路网络
• 广域网网格

这两种实现本质上都是贪婪的。

编码快乐！

关注七爪网，获取更多APP/小程序/网站源码资源！