在 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
以上是 在 Python 中使用 Prim 算法找出 MST 的程序 的全部内容， 来源链接： utcz.com/z/363240.html
