LeetCode 中等难度 - 最小生成树 (Minimum Spanning Tree)

最小生成树（Minimum Spanning Tree，简称MST）是图论中的一个重要概念。它是指在一个加权无向连通图中，包含图中所有顶点的、权值之和最小的生成树。

常见算法

  1. 克鲁斯卡尔算法（Kruskal's Algorithm）

    • 从所有边中按权重顺序选择，每次选择一条最小的边，但这条边不能构成环。
    • 时间复杂度：(O(E \log E))，其中E是边的数量。

  2. 普里姆算法（Prim's Algorithm）

    • 从一个顶点开始，逐步增加边，直到包含所有顶点。
    • 时间复杂度：(O(E \log V))，其中V是顶点的数量。

代码示例（Python）

以下是一个使用克鲁斯卡尔算法求解最小生成树的Python代码示例：

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        rootx = self.find(parent, x)
        rooty = self.find(parent, y)

        if rank[rootx] < rank[rooty]:
            parent[rootx] = rooty
        elif rank[rootx] > rank[rooty]:
            parent[rooty] = rootx
        else:
            parent[rooty] = rootx
            rank[rootx] += 1

    def kruskal_mst(self):
        result = []
        i, e = 0, 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            u, v, w = self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                e = e + 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result


g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)

print("边的权重和最小生成树：")
mst = g.kruskal_mst()
for u, v, weight in mst:
    print(f"{u} - {v} ({weight})")

扩展阅读

[

Minimum Spanning Tree
]