通用最小生成樹

Question

我正在閱讀有關Cormen等最小生成樹的信息。以下是通用最小生成樹的 。

假設我們有一個連接，無向圖G =（V，E）戕重量 函數w：E-> R和我們希望找到最小生成樹G. 這裏我們使用貪婪方法。這種貪婪策略由 採用「通用」算法捕獲，該算法一次只生成一個邊緣的最小生成樹 。該算法管理一組邊A， ，保持以下循環不變。

在每次迭代之前，A是某個最小生成樹的子集。

GENERIC-MST(G,w) 
A = NULL 
while A is not a spanning tree 
    do find an edge (u, v) that is safe for A 
    A = A ∪ {(u, v)} 
end while 

return A 

問題

1. 是什麼在不變authore意味着 「A」 是最低的一些 生成樹的子集？本聲明中的「某些」是什麼？我教過的只有一個MST。

2. 在上面的僞代碼中作者所說的「A不是生成樹」是什麼意思？ 即，循環何時以及何時退出？

3. 在「一些」最小生成樹的僞代碼中，這裏我的擴展名只有一個。 對不對？

任何人都可以用小例子來解釋一下嗎？

謝謝！

Answer 1

1.絕對不是。 MST不一定是唯一的。例如：

所有邊的權重相同。

u --- v 
|  | 
|  | 
w --- x 

上面的圖有4個MST，通過刪除任何邊緣。

2.生成樹T = (V,e)在G = (V,E)是這樣的：|e| = |V|-1

號

Answer 2

1. 當你說一個圖的生成樹是獨一無二的你是正確的。但是，當圖的所有邊長都不相同時就​​是這種情況。正如在上面的答案中所解釋的，具有相等邊長的圖可以有許多不同的生成樹（當然，它們都具有相同的總重量）。
2. 當您在生成樹中包含圖形的所有頂點時，while循環就存在。爲此，您在while循環中添加一個檢查。

Answer 3

1. 不正確的，每@davin

2. 算法認爲你有一個森林不變，但直到你補充足夠的邊緣森林不會跨越圖。因此，你必須不斷添加邊，直到它們都不安全（在這一點上循環中斷）。

3. 看到1

Answer 4

1. 這是錯誤的。即使只有兩條邊相等，圖也可能有很多MST。

2. 一個是不是因爲最小生成樹：

   2.1所有首先一個不是一棵樹 - 它是斷開的。

   2.2它不跨越圖

   當滿足上面條件時

3. 它是正確的說，它是在一些 MST因爲有許多的循環將退出。