最小生成樹資料結構的問題

我也沒有ctrl+c，ctrl+v這裡有答案，還有分析。

這種**是網際網絡上的一堆。

如果圖形邊緣的權重不同，則其最小生成樹是唯一的。

n 個點由 n-1 條邊連線，形狀只能是一棵樹。 可以這樣理解：樹的每個節點都有乙個唯一的父節點，即至少有n條邊，除了根節點，所以它是n-1條邊。

那麼，對於乙個n點加權圖，它的生成樹就是用n-1條邊來連線n個點，那麼最小生成樹就是n-1條邊的邊權總和，簡單的理解就是只用這個圖n-1條邊，n-1條邊的邊權重之和是最小的。 紅色邊是此圖的最小生成樹。

樹形圖的概念。

無圓且相連的無向圖稱為樹。 樹木通常表示為 t。 作為樹的定義，它也可以用以下方式表示：

1） T 已連線，沒有環路或環路。

2） T 未帶圓圈，有 n 條邊（如果有 n 個節點）。

3） T 與 n 1 邊連線。

4）T沒有環，但兩個彼此不相鄰的節點連線到一側，只有乙個圓。

5） t 已連線，但如果移除 t 的任何邊，則 t 未連線。（也就是說，在具有相同點集的圖形中，樹是邊最少的連線圖形。 ）

6） t 的任意兩個節點之間正好有一條主鏈。

通常先找到最小生成樹，然後找到它亞小型生成樹（具體來說，可以列舉圖上的其他邊並將它們新增到樹中，同時刪除重複的邊，並找到權重和最小邊刪除方法），如果子小生成樹的權重和不等於最小生成樹，則最小生成樹是唯一的， 否則它不是唯一的。

沒有乙個所有權值相等，或者存在相等的邊，但在構建生成樹的過程中，權重相等的邊包含在生成樹中，最小生成樹是唯一的。 - 天琴。

當加權連線圖的任何乙個環包含不同的權重時，其 MST 是唯一的。 --從王道。

任何乙個環中包含的邊緣的重量都是不同的。

最小生成樹應用於圖論知識的實際問題。 生成樹和最小生成樹具有許多重要的應用。

例如，如果要在n個城市之間鋪設光纜，主要目標是使這n個城市中的任意兩個之間進行通訊，但是鋪設光纜的成本非常高，並且鋪設光纜的成本因城市而異，因此另乙個目標是將鋪設光纜的總成本降至最低。 這需要找到最小加權生成樹。

生成樹協議的工作原理：如果在任何交換機中到達根網橋。

有兩個或多個鏈結。 生成樹協議只保留乙個交換機，切斷其他交換機，從而保證任意兩個交換機之間只有乙個活動鏈路。 由於生成的這種拓撲。

它很像以根開關為主幹的樹結構，因此稱為生成樹協議。

以上內容是指：百科全書 - 最小生成樹。

以上內容請參考：百科全書-生成樹協議。

求解最小生成樹。

方法如下：

連線圖：在無向圖中，如果任意兩個頂點 VI 和 VJ 具有相互通訊的路徑，則稱為無向圖為連線圖。

強大的連線圖。 在有向圖中，如果任意兩個頂點 VI 和 VJ 具有共同的路徑，則稱有向圖是強連線的。

連線網路：在連線圖中，如果圖的邊有一定的含義，則每條邊對應乙個數字，稱為權重; 右圖表示連線頂點的成本，這種連通性圖稱為連通性網路。

生成樹：連線圖的生成樹是乙個連線子圖，它包含圖中的所有 n 個頂點，但只有足夠的 n-1 條邊來形成樹。 具有 n 個頂點的生成樹具有且只有 n-1 條邊，如果將另一條邊新增到生成樹中，則必須對其進行迴圈。

最小生成樹：連線網路的所有生成樹中所有邊和最小生成樹的成本稱為最小生成樹。

以下是最小生成樹的一些解決方案。

Prime演算法的基本思想。

1.清除生成樹，並取任意頂點加入嵊州正城樹。

2.在乙個端點位於生成樹中而另乙個端點不在活動樹中的邊中，選擇權重最小的邊，然後將其和另乙個端點新增到生成樹中。

3.重複步驟 2，直到所有頂點都進入生成樹，生成樹是最小的生成樹。

Kruskal 演算法：構造乙個只有 n 個頂點和乙個空邊集的子圖，如果子圖中的每個頂點都看作是每棵樹的根節點，則它就是乙個有 n 棵樹的森林。

然後，從網的邊集中選擇一條權重最小的邊，如果邊的兩個頂點屬於不同的樹，則將其新增到子圖中，即將兩個頂點所在的兩棵樹合併成一棵樹。 相反，如果邊的兩個頂點落在同一棵樹上，則不建議採用權重最小的邊。 依此類推，直到森林裡只有一棵樹。

Kruskal 演算法可以在並行集的基礎上非常快速地實現。 結合算例介紹具體演算法實現（合併查詢部分的合併查詢部分可以在合併查詢部分的介紹中找到）。

生成樹的概念：連線圖g的子圖 如果它是一棵樹，其中包含g的拍攝軌跡的頂點，那麼該子圖稱為g的生成樹 生成樹是連線圖的乙個非常小的連線子圖。 所謂的最低限度：

如果隨機向樹新增一條邊，則會出現乙個迴圈; 如果刪除一條邊，則會使它程式設計為乙個斷開連線的圖。 生成樹兩側的權重之和稱為基因的權重。 權重最小的生成樹稱為最小生成樹，常用的演算法有素數演算法和kruskal演算法。

所謂的最小生成樹是具有 n 個頂點的加權連線圖 g，如果存在子圖 g'，它包含圖 g 中的所有頂點和邊的子集，不形成迴圈，並且是子圖 g'每邊的權重之和最小，稱為g'是圖 g 的最小生成樹。 從定義中，我們可以看到最小生成樹的三個屬性：

最小生成樹不能有迴圈。

最小生成樹可以是乙個，也可以是多個。

生成樹邊的最小數量等於頂點數減去 1。 在本文中，我們將介紹兩種最小生成樹演算法，即 Kruskal 演算法和 Prim 演算法。

Kruskal 演算法的核心思想是，在加權連線圖中，在邊集中不斷找到最小的邊，如果邊滿足獲得最小生成樹的條件，則構造它，直到最終獲得最小生成樹。

Kruczcard演算法的執行步驟：

第 1 步：在加權連線圖中，對邊的權重進行排序。

第 2 步：確定是否需要選擇此邊（此時，圖形中的邊已按權重從小到大的順序排列）。 判斷的依據是邊的兩個頂點是否連線，如果連線，則繼續到下乙個; 如果未連線，則選擇使其連線。

第 3 步：迴圈第二步，直到圖中的所有頂點都在同乙個連線的元件中，即獲得最小生成樹。

下面我將用圖表來說明 Kruskal 演算法的工作流程，如下圖所示：

請參閱貪婪演算法 - 最小生成樹演算法。

貪婪策略：對演算法的理解：

迴圈不變數：鍵畝。

在每個迴圈之前，a 是某個最小生成樹的子集。

安全邊：滿足以下條件的邊稱為安全邊。

將邊 （u， v） 新增到集合 a 中，使 a 不違反迴圈不變數，即 au 也是最小生成樹的子集。

在貪婪策略中識別安全邊緣的規則：

推論：如果乙個問題的最優解包含子問題的最優解，則該問題具有最優子結構。

最小生成樹滿足最優子結構，證明如下：