Prim和Kruskal的算法複雜度

Question

給定一個帶有權重的無向連通圖。 w：E - > {1,2,3,4,5,6,7} - 意思是隻有7個砝碼可能。 我需要使用O（n + m）中的Prim算法和O（m * a（m，n））中的Kruskal算法找到生成樹。

我不知道如何做到這一點，真的需要一些關於如何權重可以幫助我在這裏的指導。

Answer 1

按我的理解，它不是流行的回答家庭作業，但是這可能有希望成爲有用的其他人不只是你;）

普里姆：

普里姆是查找算法最小生成樹（MST），就像克魯斯卡爾一樣。 可視化算法的簡單方法是將圖形繪製在一張紙上。 然後，您可以在所選的所有節點上創建可移動的線（剪切）。在下面的例子中，集合A將是剪切內的節點。然後選擇穿過切口的最小邊緣，即從線內節點到外部節點。始終選擇重量最輕的邊。添加新節點後，您移動剪切，以便它包含新添加的節點。然後重複，直到所有節點都在切割中。

該算法的簡短摘要是：

1. 創建一組，A，其中將包含所選擇的verticies。它最初將包含一個由您選擇的隨機起始節點。
2. 創建另一個集合B.這將初始爲空，並用於標記所有選定的邊。
3. 選擇一條邊E（u，v），即從節點u到節點v的一條邊。邊E必須是具有最小權重的邊，其中節點u在集合A內且v不在裏面A.（如果有幾條重量相同的邊，可以隨機選擇）
4. 將邊（u，v）添加到集合B，並將v添加到集合A.
5. 重複步驟3和4直到A = V，其中V是所有頂點的集合。
6. 集合A和B現在描述您的生成樹！ MST將包含A和B內的節點將描述它們如何連接。

克魯斯卡：

克魯斯卡類似於普里姆，除非你沒有晉級。所以你總是選擇最小的邊緣。

1. 創建一個集合A，它最初是空的。它將用於存儲選定的邊緣。
2. 從集合E中選擇權重最小的邊E，這在A（u，v）=（v，u）中尚不存在，所以只能沿着一個方向移動邊。
3. 將E添加到A.
4. 重複2和3直到A和E相等，也就是說，直到您選擇了所有邊。

我不確定這些算法的確切性能，但我認爲Kruskal是O（E log E），Prim的性能是基於哪個數據結構來存儲邊緣。如果使用二進制堆，則搜索最小邊的速度比使用鄰接矩陣存儲最小邊的速度快。

希望這會有所幫助！

Answer 2

您可以更快地對邊緣權重進行排序。在Kruskal算法中，你不需要O（M lg M）排序，你可以使用count排序（或者任何其他O（M）算法）。所以最終的複雜度是O（M）用於排序，O（Ma（m））用於聯合發現階段。總共是O（Ma（m））。

對於Prim算法的情況。你不需要使用堆，你需要7個列表/隊列/數組/任何東西（有恆定的時間插入和檢索），每個重量一個。然後，當你正在尋找最便宜的傳出邊緣時，你會檢查這些列表中的一個是非空的（來自最便宜的），並使用該邊緣。由於7是一個常數，因此整個算法運行在O（M）時間。