Prim算法最小生成树代码运行输出为空问题排查

核心问题点 #

代码存在3处逻辑错误，导致无法正常输出结果：

• 初始状态未选中任何起始节点：Prim算法需要从一个初始节点启动扩展，初始化selected_nodes全为False时，第一次进入循环内层遍历永远找不到已选中的节点，无法识别有效边，逻辑直接卡死。
• 邻接边遍历范围不全：内层j循环写为range(0+i, N)，仅遍历索引大于等于i的节点，漏掉了j<i的有效邻接边，无法找到全局最小的跨集合边。
• 赋值逻辑顺序错误：先给生成树矩阵赋值再判断边是否有效，会导致无有效边时错误写入默认值，污染矩阵结果。

修正后代码 #

N = 8
inf = 99

graph = [[0,0,6,7,0,8,0,0], #节点1
         [0,0,0,3,4,2,0,0], #节点2
         [6,0,0,0,0,3,0,7], #节点3
         [7,3,0,0,9,0,0,0], #节点4
         [0,4,0,9,0,0,5,0], #节点5
         [8,2,3,0,0,0,9,3], #节点6
         [0,0,0,0,5,9,0,0], #节点7
         [0,0,7,0,0,3,0,0]] #节点8

spanning_tree_graph = [[0]*N for _ in range(N)]
selected_nodes = [False]*N
# 选中索引0的节点作为算法起始点
selected_nodes[0] = True

while False in selected_nodes:
    minimum = inf
    start = 0
    end = 0
    for i in range(N):
        if selected_nodes[i]:
            # 遍历所有节点，不限制j的索引范围
            for j in range(N):
                if not selected_nodes[j] and graph[i][j] > 0:
                    if graph[i][j] < minimum:
                        minimum = graph[i][j]
                        start, end = i, j
    # 仅当找到有效跨集合边时更新生成树
    if minimum != inf:
        selected_nodes[end] = True
        spanning_tree_graph[start][end] = minimum
        spanning_tree_graph[end][start] = minimum

print(spanning_tree_graph)

运行结果 #

[[0, 0, 6, 0, 0, 0, 0, 0], [0, 0, 0, 3, 4, 2, 0, 0], [6, 0, 0, 0, 0, 3, 0, 0], [0, 3, 0, 0, 0, 0, 0, 0], [0, 4, 0, 0, 0, 0, 5, 0], [0, 2, 3, 0, 0, 0, 0, 3], [0, 0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 0, 0, 3, 0, 0]]

说明：你提供的预期输出和当前输入的邻接矩阵边权不匹配，输入图中不存在权值为1、节点0-1连接边（权值为0）、节点2-7权值为4的边（实际权值为7），上述输出是针对你给出的8节点邻接矩阵计算得到的正确最小生成树邻接矩阵，总权值为26。

内容的提问来源于stack exchange，提问作者Nickolay