使用prim算法代码讲解

以下是Prim算法的代码讲解：

def prim(G, s):
    dist = {} # dist记录到节点的最小距离
    parent = {} # parent记录最小生成树的双亲
    visited = set() # 记录已访问的节点

    # 初始化dist和parent
    for node in G:
        dist[node] = float('inf')
        parent[node] = None

    dist[s] = 0 # 起始节点到自身的距离为0

    while len(visited) < len(G):
        # 找到dist中最小的节点
        min_node = None
        min_dist = float('inf')
        for node in G:
            if node not in visited and dist[node] < min_dist:
                min_node = node
                min_dist = dist[node]

        visited.add(min_node) # 将最小节点标记为已访问

        # 更新与最小节点相邻节点的距离和parent
        for neighbor in G[min_node]:
            if neighbor not in visited and G[min_node][neighbor] < dist[neighbor]:
                dist[neighbor] = G[min_node][neighbor]
                parent[neighbor] = min_node

    return parent

# 示例图的邻接矩阵表示
G = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 1},
    'C': {'A': 3, 'B': 1, 'D': 2},
    'D': {'B': 1, 'C': 2}
}

s = 'A' # 起始节点为A
parent = prim(G, s)
print("最小生成树的双亲节点：", parent)

该代码实现了Prim算法，用于找到一个无向图的最小生成树。算法通过贪心策略，从起始节点开始，逐步选择与当前生成树距离最小的节点，并将其加入生成树中。最终得到的parent字典记录了每个节点在最小生成树中的双亲节点。