Minimum Spanning Tree 最小生成樹
最小生成樹（Minimum Spanning Tree，簡稱MST）是一種在圖論中經常使用的概念。它主要應用於網絡設計、路徑規劃、運輸等問題。在給定的連接網絡（可以是無向的或有向的）中，每個節點（或稱為頂點）都與其他節點相連，並且每個連接（或稱為邊）都有一個相對應的權重或成本。一個生成樹（Spanning Tree）是該網絡的一個子圖，它包括網絡中的所有節點，並且是連通的（也就是說，從任何一個節點都可以到達其他任何節點）。
當我們說“最小”生成樹時，我們指的是權重（或成本）之和最小的生成樹。也就是說，最小生成樹是連接所有節點，且其邊的權重總和最小的樹。
建立最小生成樹的常見算法包括普林算法（Prim's algorithm）和克魯斯克爾算法（Kruskal's algorithm）。這兩種算法都利用了貪婪策略，每次選擇局部最佳解，最終得到全局最佳解。
最小生成樹在許多實際情況中都非常有用。例如，考慮一個需要連接多個城市的電力網絡。在這種情況下，最小生成樹可以幫助我們找到連接所有城市，且總成本最低的路線。
Disjoint Set
Disjoint Set，也稱為聯合-查找資料結構（Union-Find Data Structure），是一種數據結構，用於管理一個分離的元素的集合。這種數據結構支持兩種操作：聯合（Union）和查找（Find）。
聯合（Union）：聯合是一種操作，它將兩個集合合併成一個新的集合。這通常是通過將一個集合的代表元素（可以是任何元素，但通常是集合中的第一個元素或“根”元素）指向另一個集合的代表元素來實現的。
查找（Find）：查找操作對於給定的元素找到其所屬的集合。這是通過跟蹤指向代表元素的指針來實現的。
為了提高效率，並查集通常使用兩種技術：路徑壓縮（Path Compression）和聯合按秩（Union by Rank）。
路徑壓縮：當我們進行查找操作時，路徑壓縮會使我們經過的每個節點直接指向代表元素。這可以加快未來查找操作的速度。
聯合按秩：當我們進行聯合操作時，我們可以根據集合的“秩”（即元素數量或集合的高度）來決定哪一個代表元素指向另一個。我們總是讓秩較小的集合指向秩較大的集合。這樣可以保持樹的高度盡可能的小，從而加快查找操作的速度。
並查集在許多演算法中都非常有用，例如克魯斯克爾最小生成樹演算法，以及用於解決連通性問題的演算法。
頁:
[1]