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

假设我们得到一个图并要求从该图中找出“最小生成树”(MST)。图的 MST 是加权图的子集，其中所有顶点都存在并连接，并且子集中不存在环。MST 被称为最小值，因为 MST 的总边权重是图中可能的最小值。所以，这里我们使用 Prim 的 MST 算法，从给定的图中找出 MST 的总边权重。

所以，如果输入像

，顶点数(n)为4，起始顶点(s)=3，则输出为14。

该图中的 MST 将是这个 -

此 MST 的总边权重为 14。

示例

让我们看看以下实现以更好地理解 -

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