資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用Python實現Prim演算法求解最小生成樹的程式
假設我們得到一個圖，並要求從中找到“最小生成樹”（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
- while True:
- min_weight := 無窮大
- m_idx := -1
- for i in range(0, G的大小):
- if itr[i] == False:
- if distance[i] < min_weight:
- min_weight := distance[i]
- m_idx := i
- if distance[i] < min_weight:
- if itr[i] == False:
- if m_idx == -1:
- 跳出迴圈
- c := c + min_weight
- itr[m_idx] := True
- 對於 G[m_idx] 的每個值對 (i, j):
- distance[i] := min(distance[i], j)
- return c
- G := 一個包含 n 個其他對映的新對映
- 對於 edges 中的每個專案：
- 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
- return 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
更新於：2021年10月6日
2K+ 次瀏覽
廣告