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

算法

解决最小生成树问题常用的算法有：

  • Prim算法
  • Kruskal算法

下面分别介绍这两种算法。

Prim算法

Prim算法是一种贪心算法，它从一个顶点开始，逐步增加边，直到所有顶点都被包含在生成树中。

  1. 选择一个顶点作为起点。
  2. 将该顶点加入生成树中。
  3. 从生成树中找到一个与未加入生成树的顶点相连的最小权值边，将该边加入生成树中。
  4. 重复步骤3，直到所有顶点都被包含在生成树中。

Kruskal算法

Kruskal算法也是一种贪心算法，它按照边的权值大小进行排序，然后逐步选择边，直到所有顶点都被包含在生成树中。

  1. 将所有边按照权值大小进行排序。
  2. 遍历排序后的边，对于每条边：
    • 如果这条边不会形成环，则将其加入生成树中。
    • 如果这条边会形成环，则跳过这条边。
  3. 重复步骤2，直到所有顶点都被包含在生成树中。

代码示例

以下是一个使用Prim算法求解最小生成树的Python代码示例：

def prim(graph):
    n = len(graph)
    mst = [[0] * n for _ in range(n)]
    visited = [False] * n
    min_edge = [float('inf')] * n
    min_edge[0] = 0
    for i in range(n):
        u = min_edge.index(min(min_edge))
        visited[u] = True
        for v in range(n):
            if not visited[v] and graph[u][v] < min_edge[v]:
                min_edge[v] = graph[u][v]
                mst[u][v] = 1
                mst[v][u] = 1
    return mst

# 示例图
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

# 输出最小生成树
mst = prim(graph)
for row in mst:
    print(row)

扩展阅读

更多关于最小生成树的信息，请访问本站图论教程。

Minimum Spanning Tree