使用 Python 中的 Prim 算法查找 MST 的程序
pythonserver side programmingprogramming更新于 2025/12/2 14:36:17
假设我们给出一个图，并被要求从该图中找到"最小生成树"(MST)。图的 MST 是加权图的子集，其中所有顶点都存在且连接，并且子集中不存在循环。MST 被称为最小，因为 MST 的总边权重是图中可能的最小值。因此，我们在这里使用 Prim 的 MST 算法，从给定的图中找出 MST 的总边权重。
因此，如果输入如下
，顶点数 (n) 为 4，起始顶点 (s) = 3，则输出将为 14。
此图中的 MST 将为此 −
此 MST 的总边权重为 14。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个函数 mst_find() 。这将需要 G，s
- distance := 一个大小为 G 的新列表，初始化值为负无穷大
- distance[s] := 0
- itr := 一个大小为 G 的新列表，初始化值为 False
- c := 0
- 当 True 时，执行
- min_weight := 无穷大
- m_idx := -1
- 对于范围从 0 到 G 大小的 i，执行
- 如果 itr[i] 与 False 相同，则
- 如果 distance[i] < min_weight，则
- min_weight := distance[i]
- m_idx := i
- 如果 distance[i] < min_weight，则
- 如果 itr[i] 与 False 相同，则
- 如果 m_idx 与 -1 相同，则
- 退出循环
- c := c + min_weight
- itr[m_idx] := True
- 对于 G[m_idx] 值中的每一对 i、j，执行
- distance[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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
