最小伸展樹

最小伸展樹（Minimum Spanning Tree, MST）是一種數據結構，用於表示一個連通圖的所有頂點之間的最短路徑。在圖論中，伸展樹是一種特殊的樹形結構，它包含了一個圖的所有頂點，並且邊的權值總和最小。最小伸展樹的問題是找到一個連通圖的所有頂點之間的最短路徑，同時保證這些路徑的總權值最小。

最小伸展樹的應用非常廣泛，例如在電力網路的設計中，需要找到一組電纜，將所有的變電站連接起來，同時最小化電纜的總長度。在通訊網路的設計中，需要找到一組線路，將所有的交換機連接起來，同時最小化線路的總長度。在物流網路的設計中，需要找到一組路線，將所有的倉庫連接起來，同時最小化路線的總長度。

最小伸展樹的算法有很多種，其中最著名的是普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法。普里姆算法是一種貪心算法，它從圖中的一個頂點開始，逐漸擴展到其他的頂點，直到所有的頂點都被包含在伸展樹中。克魯斯卡爾算法是一種分治算法，它將圖中的邊按照權值從小到大排序，然後逐個加入邊，直到所有的頂點都被包含在伸展樹中。

最小伸展樹的時間複雜度取決於算法和圖的結構。普里姆算法的時間複雜度是 O(E log V)，其中 E 是邊的數量，V 是頂點的數量。克魯斯卡爾算法的時間複雜度是 O(E alpha(E, V))，其中 alpha(E, V) 是E 和 V 的極小上界函數，通常情況下，alpha(E, V) 的增長速度比 log V 慢。