# 导入 heapq 模块，用于实现最小堆（优先队列）
import heapq

def prim(graph, start):
    """
    使用 Prim 算法计算最小生成树（MST）

    参数：
    graph - 图的邻接表表示，格式为 {节点: [(邻居节点, 边的权重), ...]}
    start - 起始节点

    返回：
    mst - 最小生成树的边集合，格式为 [(节点1, 节点2, 权重), ...]
    total_weight - 最小生成树的总权重
    """

    # 初始化最小生成树的边集合为空列表
    mst = []
    # 初始化最小生成树的总权重为 0
    total_weight = 0

    # 创建一个集合来存储已访问过的节点，初始时只包含起始节点
    visited = set([start])

    # 创建一个最小堆（优先队列）来存储候选边，初始为空
    min_heap = []

    # 将起始节点的所有边加入最小堆
    # 遍历起始节点的所有邻居节点
    for neighbor, weight in graph[start]:
        # 将边的信息作为元组 (权重, 起始节点, 目标节点) 加入最小堆
        heapq.heappush(min_heap, (weight, start, neighbor))

    # 当最小堆不为空时，继续循环
    while min_heap:
        # 从最小堆中弹出权重最小的边
        weight, frm, to = heapq.heappop(min_heap)

        # 如果目标节点已经被访问过，跳过该边（避免形成环）
        if to in visited:
            continue

        # 将该边加入最小生成树的边集合
        mst.append((frm, to, weight))
        # 更新最小生成树的总权重
        total_weight += weight
        # 将目标节点标记为已访问
        visited.add(to)

        # 遍历目标节点的所有邻居节点
        for neighbor, w in graph[to]:
            # 如果邻居节点未被访问过，将边加入最小堆
            if neighbor not in visited:
                heapq.heappush(min_heap, (w, to, neighbor))

    # 返回最小生成树的边集合和总权重
    return mst, total_weight

# 测试代码
if __name__ == "__main__":
    # 定义图，使用邻接表表示，每个节点对应一个列表，列表中包含其邻居节点和边的权重
    graph = {
        'A': [('B', 1), ('C', 3), ('D', 4)],
        'B': [('A', 1), ('C', 2), ('D', 5)],
        'C': [('A', 3), ('B', 2), ('D', 6)],
        'D': [('A', 4), ('B', 5), ('C', 6)],
    }

    # 调用 prim 函数，指定起始节点为 'A'
    mst, total_weight = prim(graph, 'A')

    # 输出最小生成树的边
    print("最小生成树的边：")
    # 遍历最小生成树的边集合
    for edge in mst:
        # edge 是一个包含 (起始节点, 目标节点, 权重) 的元组
        print(f"{edge[0]} - {edge[1]} 权重: {edge[2]}")

    # 输出最小生成树的总权重
    print(f"最小生成树的总权重: {total_weight}")

1. 初始化变量

mst：用于存储最小生成树的边集合。
total_weight：用于累加最小生成树的总权重。
visited：使用集合存储已访问的节点，初始化时只包含起始节点。
min_heap：创建一个空的最小堆，用于存储候选边。

2. 将起始节点的边加入最小堆

for neighbor, weight in graph[start]:
    heapq.heappush(min_heap, (weight, start, neighbor))

遍历起始节点的所有邻居，将每条边的 (权重, 起始节点, 目标节点) 加入最小堆。

主循环

while min_heap:
    # 循环体

当最小堆不为空时，不断从中取出权重最小的边。

弹出最小边并处理

weight, frm, to = heapq.heappop(min_heap)
if to in visited:
    continue
mst.append((frm, to, weight))
total_weight += weight
visited.add(to)

使用 heapq.heappop() 从最小堆中弹出权重最小的边。
如果目标节点已经访问过，跳过该边。
否则，将该边加入 mst，累加权重，并将目标节点标记为已访问。

将新节点的边加入最小堆

for neighbor, w in graph[to]:
    if neighbor not in visited:
        heapq.heappush(min_heap, (w, to, neighbor))

遍历新加入的目标节点的所有邻居。
如果邻居节点未被访问过，将对应的边加入最小堆。

返回结果

return mst, total_weight

返回最小生成树的边集合和总权重。

other

6. 算法的伪代码

以下是 Prim 算法的伪代码：

初始化一个空生成树 T
选择一个起始节点 v0 并加入 T
while T 中的节点数 < 所有节点数:
    找到 T 中的节点到未连接节点的最小边 (u, v)
    将边 (u, v) 和节点 v 加入 T

7. 复杂度

如果使用邻接矩阵存储图，Prim算法的时间复杂度是 $O(V^2)$ ，其中 $V$ 是节点数；如果使用优先队列和邻接表存储图，可以将复杂度优化到 $O(E \log V)$ ，适用于稀疏图。

总结

Prim算法通过逐步选择最小的连接边来生成最小生成树。这个过程每次选择当前生成树的最小边，最终生成最低成本的连接方案。

好的，我将带您一步一步地手动计算 Prim 算法在给定图上的执行过程，以验证算法的正确性。我们将使用之前提供的 Python 代码中的图，并详细解释每一步骤中的变量和数据结构的变化。

给定图

我们有一个加权无向连通图，节点为 'A'、'B'、'C'、'D'，边和权重如下：

A - B，权重 1
A - C，权重 3
A - D，权重 4
B - C，权重 2
B - D，权重 5
C - D，权重 6

图的邻接表表示：

graph = {
    'A': [('B', 1), ('C', 3), ('D', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 3), ('B', 2), ('D', 6)],
    'D': [('A', 4), ('B', 5), ('C', 6)],
}

Prim 算法手动计算步骤

初始化：

已访问节点集（visited）：包含起始节点 'A'
visited = {'A'}
最小生成树的边集合（mst）：空
mst = []
最小生成树的总权重（total_weight）：0
total_weight = 0
最小堆（优先队列）（min_heap）：空
min_heap = []

将起始节点 'A' 的所有边加入最小堆：

将边 (1, 'A', 'B') 加入 min_heap
将边 (3, 'A', 'C') 加入 min_heap
将边 (4, 'A', 'D') 加入 min_heap

min_heap 状态：

[(1, 'A', 'B'), (3, 'A', 'C'), (4, 'A', 'D')]

第 1 次迭代

从 min_heap 中弹出权重最小的边：

弹出 (1, 'A', 'B')

检查目标节点 'B' 是否已访问：

'B' 未被访问

操作：

将边 ('A', 'B', 1) 加入 mst
mst = [('A', 'B', 1)]
更新 total_weight
total_weight = 1
将节点 'B' 加入 visited
visited = {'A', 'B'}

将新节点 'B' 的未访问邻居的边加入 min_heap：

邻居 'A' 已访问，跳过
邻居 'C' 未访问，加入 (2, 'B', 'C')
邻居 'D' 未访问，加入 (5, 'B', 'D')

min_heap 状态：

[(2, 'B', 'C'), (3, 'A', 'C'), (4, 'A', 'D'), (5, 'B', 'D')]

第 2 次迭代

从 min_heap 中弹出权重最小的边：

弹出 (2, 'B', 'C')

检查目标节点 'C' 是否已访问：

'C' 未被访问

操作：

将边 ('B', 'C', 2) 加入 mst
mst = [('A', 'B', 1), ('B', 'C', 2)]
更新 total_weight
total_weight = 3
将节点 'C' 加入 visited
visited = {'A', 'B', 'C'}

将新节点 'C' 的未访问邻居的边加入 min_heap：

邻居 'A' 已访问，跳过
邻居 'B' 已访问，跳过
邻居 'D' 未访问，加入 (6, 'C', 'D')

min_heap 状态：

[(3, 'A', 'C'), (5, 'B', 'D'), (4, 'A', 'D'), (6, 'C', 'D')]

注意： Python 的 heapq 模块实现的是最小堆，弹出元素时按照第一个元素（权重）排序。当权重相同时，按照后续元素的顺序。

第 3 次迭代

从 min_heap 中弹出权重最小的边：

弹出 (3, 'A', 'C')

检查目标节点 'C' 是否已访问：

'C' 已被访问

操作：

跳过该边，不进行任何操作

min_heap 状态：

[(4, 'A', 'D'), (5, 'B', 'D'), (6, 'C', 'D')]

第 4 次迭代

从 min_heap 中弹出权重最小的边：

弹出 (4, 'A', 'D')

检查目标节点 'D' 是否已访问：

'D' 未被访问

操作：

将边 ('A', 'D', 4) 加入 mst
mst = [('A', 'B', 1), ('B', 'C', 2), ('A', 'D', 4)]
更新 total_weight
total_weight = 7
将节点 'D' 加入 visited
visited = {'A', 'B', 'C', 'D'}

将新节点 'D' 的未访问邻居的边加入 min_heap：

邻居 'A' 已访问，跳过
邻居 'B' 已访问，跳过
邻居 'C' 已访问，跳过

min_heap 状态：

[(5, 'B', 'D'), (6, 'C', 'D')]

第 5 次迭代

从 min_heap 中弹出权重最小的边：

弹出 (5, 'B', 'D')

检查目标节点 'D' 是否已访问：

'D' 已被访问

操作：

跳过该边，不进行任何操作

min_heap 状态：

[(6, 'C', 'D')]

第 6 次迭代

从 min_heap 中弹出权重最小的边：

弹出 (6, 'C', 'D')

检查目标节点 'D' 是否已访问：

'D' 已被访问

操作：

跳过该边，不进行任何操作

min_heap 状态：

[]

结束条件：

min_heap 为空
所有节点都已被访问（'A'、'B'、'C'、'D'）

最终的最小生成树（mst）：

[('A', 'B', 1), ('B', 'C', 2), ('A', 'D', 4)]

最小生成树的总权重（total_weight）：

1 + 2 + 4 = 7

总结

通过手动计算，我们验证了 Prim 算法在该图上的执行过程，与之前运行代码的结果一致：

最小生成树的边：
- A - B，权重 1
- B - C，权重 2
- A - D，权重 4
最小生成树的总权重：7

变量和数据结构的状态变化总结

迭代次数	弹出的边	是否加入 mst	更新后的 mst	visited	min_heap 状态
初始化	-	-	[]	{'A'}	[(1, 'A', 'B'), (3, 'A', 'C'), (4, 'A', 'D')]
1	(1, 'A', 'B')	是	[('A', 'B', 1)]	{'A', 'B'}	[(2, 'B', 'C'), (3, 'A', 'C'), (4, 'A', 'D'), (5, 'B', 'D')]
2	(2, 'B', 'C')	是	[('A', 'B', 1), ('B', 'C', 2)]	{'A', 'B', 'C'}	[(3, 'A', 'C'), (5, 'B', 'D'), (4, 'A', 'D'), (6, 'C', 'D')]
3	(3, 'A', 'C')	否（已访问）	无变化	无变化	[(4, 'A', 'D'), (5, 'B', 'D'), (6, 'C', 'D')]
4	(4, 'A', 'D')	是	[('A', 'B', 1), ('B', 'C', 2), ('A', 'D', 4)]	{'A', 'B', 'C', 'D'}	[(5, 'B', 'D'), (6, 'C', 'D')]
5	(5, 'B', 'D')	否（已访问）	无变化	无变化	[(6, 'C', 'D')]
6	(6, 'C', 'D')	否（已访问）	无变化	无变化	[]

验证

通过以上详细的手动计算，我们确认：

算法正确地选择了最小的边来构建最小生成树。
最终得到的最小生成树包含所有节点且总权重最小。

这验证了之前代码的正确性，也帮助理解了 Prim 算法的执行过程。

附加说明

**最小堆（min_heap）的作用：**在每次迭代中，高效地选择当前可用的权重最小的边。
**已访问节点集（visited）的作用：**避免形成环，确保算法不会重复访问已经包含在最小生成树中的节点。
**跳过已访问节点的边：**如果目标节点已经在 visited 中，意味着从当前生成树到该节点的更小权重的边已经被选择，因此可以安全地跳过。

公众号：AI悦创【二维码】

AI悦创·编程一对一

AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh

C++ 信息奥赛题解，长期更新！长期招收一对一中小学信息奥赛集训，莆田、厦门地区有机会线下上门，其他地区线上。微信：Jiabcdefh

方法一：QQ

方法二：微信：Jiabcdefh