贪心算法 - 最小生成树 - Prim 和 Kruskal 算法的贪心思想

贪心算法 - 最小生成树 - Prim 和 Kruskal 算法的贪心思想

一、引言

在图论的世界里，最小生成树（MST, Minimum Spanning Tree）是一个非常重要的概念。它在众多领域都有着广泛的应用，比如网络布线、交通规划等。为了求解最小生成树问题，人们提出了多种算法，其中 Prim 算法和 Kruskal 算法是基于贪心思想的经典算法。接下来，我们将深入探讨这两种算法的贪心思想以及它们的具体实现。

二、贪心算法概述

贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的算法。贪心算法并不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优选择。虽然贪心算法不能保证得到全局最优解，但对于很多问题，它可以得到最优解或者近似最优解。最小生成树问题就是贪心算法能够得到全局最优解的典型例子。

三、最小生成树问题定义

给定一个无向连通带权图 (G=(V, E))，其中 (V) 是顶点集合，(E) 是边集合。最小生成树是图 (G) 的一个子图，它是一棵包含图中所有顶点的树，并且所有边的权值之和最小。

四、Prim 算法的贪心思想与实现

（一）贪心思想

Prim 算法从一个任意顶点开始，逐步扩展生成树，每次都选择与当前生成树相连的边中权值最小的边，将对应的顶点加入到生成树中，直到所有顶点都被包含在生成树中。其贪心策略是在每一步都尽可能选择权值最小的边来扩展生成树。

（二）算法步骤

1. 初始化：选择一个任意顶点作为起始点，将其加入到生成树的顶点集合 (U) 中。
2. 选择边：在所有连接 (U) 中顶点和 (V - U) 中顶点的边中，选择权值最小的边 ((u, v))，其中 (u \in U)，(v \in V - U)。
3. 扩展生成树：将顶点 (v) 加入到 (U) 中，并将边 ((u, v)) 加入到生成树的边集合中。
4. 重复步骤 2 和 3，直到 (U = V)。

（三）示例

假设有一个包含 5 个顶点的无向连通带权图，其邻接矩阵如下：

我们从顶点 0 开始执行 Prim 算法：

1. 初始时，(U = {0})。
2. 与顶点 0 相连的边有 ((0, 1)) 权值为 2，((0, 2)) 权值为 3，选择权值最小的边 ((0, 1))，将顶点 1 加入到 (U) 中，此时 (U = {0, 1})。
3. 现在考虑连接 (U) 和 (V - U) 的边，有 ((0, 2)) 权值为 3，((1, 2)) 权值为 4，((1, 3)) 权值为 7，选择权值最小的边 ((0, 2))，将顶点 2 加入到 (U) 中，此时 (U = {0, 1, 2})。
4. 继续选择，选择边 ((2, 3)) 权值为 5，将顶点 3 加入到 (U) 中，此时 (U = {0, 1, 2, 3})。
5. 最后选择边 ((2, 4)) 权值为 6，将顶点 4 加入到 (U) 中，此时 (U = {0, 1, 2, 3, 4})，算法结束。最小生成树的边集合为 ({(0, 1), (0, 2), (2, 3), (2, 4)})，权值之和为 (2 + 3 + 5 + 6 = 16)。

（四）代码实现（Python）

import sys
def prim(graph):
    num_vertices = len(graph)
    # 记录每个顶点是否已经加入生成树
    visited = [False] * num_vertices
    # 记录每个顶点到生成树的最小权值
    key = [sys.maxsize] * num_vertices
    # 记录每个顶点的父节点
    parent = [-1] * num_vertices
    # 从顶点 0 开始
    key[0] = 0
    for _ in range(num_vertices):
        # 选择距离生成树最近的顶点
        min_key = sys.maxsize
        min_index = -1
        for v in range(num_vertices):
            if not visited[v] and key[v] < min_key:
                min_key = key[v]
                min_index = v
        # 将该顶点加入生成树
        visited[min_index] = True
        # 更新与该顶点相邻的顶点的距离
        for v in range(num_vertices):
            if graph[min_index][v] > 0 and not visited[v] and graph[min_index][v] < key[v]:
                key[v] = graph[min_index][v]
                parent[v] = min_index
    # 输出最小生成树的边
    for i in range(1, num_vertices):
        print(f"Edge: {parent[i]} - {i}, Weight: {graph[i][parent[i]]}")
    # 输出最小生成树的权值之和
    total_weight = sum(key)
    print(f"Total weight of MST: {total_weight}")
# 测试代码
graph = [
    [0, 2, 3, 0, 0],
    [2, 0, 4, 7, 0],
    [3, 4, 0, 5, 6],
    [0, 7, 5, 0, 8],
    [0, 0, 6, 8, 0]
]
prim(graph)

五、Kruskal 算法的贪心思想与实现

（一）贪心思想

Kruskal 算法将图中的所有边按照权值从小到大进行排序，然后依次选择权值最小的边，如果这条边加入到生成树中不会形成环，则将其加入到生成树中，直到生成树包含所有顶点。其贪心策略是在每一步都选择权值最小且不会形成环的边。

（二）算法步骤

1. 对图中的所有边按照权值从小到大进行排序。
2. 初始化一个空的边集合作为生成树的边集合。
3. 依次遍历排序后的边：
   • 如果这条边加入到生成树中不会形成环，则将其加入到生成树的边集合中。
   • 重复步骤 3，直到生成树包含所有顶点。

（三）示例

还是以上面的图为例，将所有边按照权值从小到大排序：
| 边 | 权值 |
|—-|—-|
| ((0, 1)) | 2 |
| ((0, 2)) | 3 |
| ((1, 2)) | 4 |
| ((2, 3)) | 5 |
| ((2, 4)) | 6 |
| ((1, 3)) | 7 |
| ((3, 4)) | 8 |

依次选择边：

1. 选择边 ((0, 1))，不会形成环，加入生成树。
2. 选择边 ((0, 2))，不会形成环，加入生成树。
3. 选择边 ((2, 3))，不会形成环，加入生成树。
4. 选择边 ((2, 4))，不会形成环，加入生成树。此时生成树已经包含所有顶点，算法结束。最小生成树的边集合为 ({(0, 1), (0, 2), (2, 3), (2, 4)})，权值之和为 (2 + 3 + 5 + 6 = 16)。

（四）代码实现（Python）

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        if self.parent[x]!= x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x!= root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
            return True
        return False
def kruskal(graph):
    num_vertices = len(graph)
    edges = []
    # 提取所有边
    for i in range(num_vertices):
        for j in range(i + 1, num_vertices):
            if graph[i][j] > 0:
                edges.append((i, j, graph[i][j]))
    # 按照权值从小到大排序
    edges.sort(key=lambda x: x[2])
    disjoint_set = DisjointSet(num_vertices)
    mst_edges = []
    total_weight = 0
    for edge in edges:
        u, v, weight = edge
        if disjoint_set.union(u, v):
            mst_edges.append(edge)
            total_weight += weight
    # 输出最小生成树的边
    for edge in mst_edges:
        u, v, weight = edge
        print(f"Edge: {u} - {v}, Weight: {weight}")
    # 输出最小生成树的权值之和
    print(f"Total weight of MST: {total_weight}")
# 测试代码
graph = [
    [0, 2, 3, 0, 0],
    [2, 0, 4, 7, 0],
    [3, 4, 0, 5, 6],
    [0, 7, 5, 0, 8],
    [0, 0, 6, 8, 0]
]
kruskal(graph)

六、Prim 算法和 Kruskal 算法的比较

七、结论

Prim 算法和 Kruskal 算法都是基于贪心思想的求解最小生成树问题的有效算法。它们的贪心策略不同，但都能得到全局最优解。在实际应用中，我们可以根据图的稠密程度选择合适的算法。如果图是稠密图，Prim 算法可能更合适；如果图是稀疏图，Kruskal 算法可能更高效。通过深入理解这两种算法的贪心思想，我们可以更好地解决相关的实际问题。