Prim算法的動態位置

Question

假設你有一個輸入文件：

<total vertices> 
<x-coordinate 1st location><y-coordinate 1st location> 
<x-coordinate 2nd location><y-coordinate 2nd location> 
<x-coordinate 3rd location><y-coordinate 3rd location> 
... 

如何Prim算法被用來尋找MST這些地點？我明白這個問題通常使用鄰接矩陣來解決。如果適用的話，任何引用都會很棒。

Answer 1

如果你已經知道prim，那很簡單。創建鄰接矩陣adj [i] [j] =位置i和位置j之間的距離

Answer 2

我只是要描述Prim's的某些實現，並希望能夠讓您獲得某個位置。

首先，您的問題並未指定如何將邊緣輸入到程序中。您有頂點的總數和這些頂點的位置。你怎麼知道哪些連接？

假設你有邊（以及這些邊的權重，就像@doomster上面說的，它可能是點之間的平面距離，因爲它們是座標），我們可以開始考慮我們的實現。維基百科的描述導致三種不同的運行時間三種不同的數據結構：http://en.wikipedia.org/wiki/Prim「s_algorithm＃Time_complexity

最簡單的是鄰接矩陣。正如您從名稱中猜測的那樣，矩陣描述了「相鄰」的節點。確切地說，有|v|行和列（其中|v|是頂點的數量）。在adjacencyMatrix[i][j]的值取決於使用情況。在我們的例子中，它是節點i和j之間的邊的權重（即距離）（這意味着您需要以某種方式對頂點進行索引。例如，您可以將頂點添加到列表中並使用它們在列表）。

現在用這個鄰接矩陣我們的算法如下：

1. 創建一個包含所有頂點，用「距離」鍵控字典。最初所有節點的距離都是無限的。
2. 創建另一個字典來跟蹤「父母」。我們用它來生成MST。跟蹤邊緣更自然，但通過跟蹤「父母」實際上更容易實現。請注意，如果您爲樹建立根（即將某個節點指定爲根），則每個節點（除根以外）都只有一個父節點。所以通過製作這本父母的字典，我們將擁有我們的MST！
3. 用原始列表隨機選擇一個節點v創建一個新列表。
   1. 從距離字典中移除v，並將其添加到父字典中，並將null作爲其父字符（即它是「根」）。
   2. 遍歷該節點的鄰接矩陣中的行。對於連接的任何節點w（對於非連接節點，您必須將它們的鄰接矩陣值設置爲某個特定值，例如0，-1，int max等）將其詞典中的「距離」更新爲adjacencyMatrix[v][w]。這個想法是，它不再「無限遙遠」......我們知道我們可以從v那裏得到。
4. 儘管詞典不是空的（即，同時也有節點，我們仍然需要連接到）
   1. 過目字典，找到的最小距離頂點x
   2. 將它添加到我們的新頂點的列表
   3. 對於每一個鄰國，更新距離爲min(adjacencyMatrix[x][neighbor], distance[neighbor])，並且還將其父母更新爲x。基本上，如果有一個更快的方法去neighbor那麼距離字典應該更新以反映;如果我們然後將neighbor添加到新列表中，我們知道我們實際添加了哪條邊（因爲父字典表示其父爲x）。
5. 我們完成了。輸出你想要的MST（你需要的所有東西都包含在父母字典中）

我承認從維基百科頁面到實際實現有一點飛躍，如上所述。我認爲解決這個差距的最好辦法就是強制執行代碼。我的意思是，如果僞代碼表示「找到min [blah]，使[foo]爲真」，那麼寫下你需要的任何代碼來執行它，然後用一個單獨的方法來粘貼它。它肯定會效率低下，但這將是一個有效的實現。圖算法的問題是有30種方法來實現它們，並且它們在性能上都非常不同;維基百科頁面只能從概念上描述算法。好處是，一旦你實現了的一些的方式，你可以快速找到優化（「哦，如果我在這個單獨的數據結構中跟蹤這種狀態，我可以使這種查找方式更快！」）。順便說一句，這是O(|V|^2)的運行時間。我懶得對細節的分析，但鬆散這是因爲：

1. 所有初始化O(|V|)在糟糕
2. 我們做循環O(|V|)時間，並採取O(|V|)時間來看看在字典中找到的最低點。所以基本上多次查找最小節點的總時間是O(|V|^2)。
3. 更新距離字典需要的時間是O(|E|)，因爲我們只處理每個邊一次。由於|E|是O(|V|^2)這也是父母的O(|V|^2)
4. 飼養軌道O(|V|)
5. 輸出樹O(|V| + |E|) = O(|E|)在最壞的情況
6. 添加所有的這些我們得到（他們都不應該只是內（2）相乘） O(|V|^2)

堆的實現是O(|E|log(|V|)它和上面非常非常相似。唯一的區別是更新的距離是O(log|V|)而不是O(1)（因爲它是一堆），但找到/刪除最小元素是O(log|V|)而不是O(|V|)（因爲它是一堆）。時間複雜度在分析上非常相似，您最終會根據需要得到類似O(|V|log|V| + |E|log|V|) = O(|E|log|V|)的東西。

其實......我有點困惑爲什麼鄰接矩陣實現關心它是一個鄰接矩陣。它也可以使用鄰接列表來實現。我認爲關鍵部分是你如何存儲距離。我可能會在上面列出的實現中脫穎而出，但我確定它實現了Prim的算法，它滿足維基百科概述的時間複雜性約束。