使用Prim算法在Python中找到MST的程序

假设我们有一个图，并要求从该图中找出’Minimum Spanning Tree’（MST）。图的MST是加权图的子集，其中所有顶点都存在且相互连接，子集中不存在环。MST被称为最小，因为MST的总边权是来自图的最小可能值。因此，在此处，我们使用Prim’s MST算法，从给定的图中找到MST的总边权。

如果输入如下图所示：

，顶点数（n）为4，起始顶点（s）= 3，则输出将为14。

这个图的MST如下：

此MST的总边权为14。

要解决这个问题，我们将遵循以下步骤 –

• 定义一个名为mst_find()的函数。这将获取G，s
  • 距离：具有G初始化的新列表的大小，初始化为负无穷大
  • distance[s] ：0
  • itr：具有G初始化的新列表的大小，初始化为False
  • c：0
  • while True，do
    • min_weight：无穷大
    • m_idx：-1
    • for i in range从0到G的大小，do
    • if itr[i]与False相同，则
      • if distance[i] ＜ min_weight，则
      • min_weight ：=距离[i]
      • m_idx ：= i
    • 如果m_idx与-1相同，则
    • 从循环中退出
    • c ：= c + min_weight
    • itr [m_idx]：= True
    • 对于G[m_idx]的每一对i，j，
    • 距离[i]：＝distance[i]，j的最小值
  • 返回c
• G：包含n个其他映射的新映射
• 对于每个条目的边缘，执行以下操作
  • u：item [0]
  • v：item [1]
  • w：item [2]
  • u：= u-1
  • v：= v-1
  • min_weight = min（G [u，v]，w）
  • G [u，v]：= min_weight
  • G [v，u]：= min_weight
• 返回mst_find（G，s）

示例

让我们看看以下实现以获得更好的理解 –

def mst_find(G, s):
    distance = [float("inf")] * len(G)
    distance[s] = 0
    itr = [False] * len(G)
    c =0
    while True:
        min_weight = float("inf")
        m_idx = -1
        for i in range(len(G)):
            if itr[i] == False:
                if distance[i] ＜ min_weight:
                    min_weight = distance[i]
                    m_idx = i
        if m_idx == -1:
            break
        c += min_weight
        itr[m_idx] = True
        for i, j in G[m_idx].items():
            distance[i] = min(distance[i], j)
    return c
               
def solve(n, edges, s):
    G = {i: {} for i in range(n)}
    for item in edges:
        u = item[0]
        v = item[1]
        w = item[2]
        u -= 1
        v -= 1
        try:
            min_weight = min(G[u][v], w)
            G[u][v] = min_weight
            G[v][u] = min_weight
        except KeyError:
            G[u][v] = w
            G[v][u] = w
    return mst_find(G, s)

print(solve(4, [(1, 2, 5), (1, 3, 5), (2, 3, 7), (1, 4, 4)], 3))

输入

4, [(1, 2, 5), (1, 3, 5), (2, 3, 7), (1, 4, 4)], 3

输出

14