最小生成樹演算法的源程式，以及最小生成樹可以在哪些欄位中使用

呵呵，這兩天我一直在做這個東西，剛好是網上看的別人，我覺得挺好的，思路比較清晰，資料結構設計也很好，很容易理解prim演算法包括使用命名空間std; #define maxvex 10#define max 65000typedef char vextype;typedef float adjtype;struct graphmatrix; struct edge; void edgecopy(edge *to,edge *from) void prim(graphmatrix *pgraph,edge *mst) for(i=0;in-1;++i)

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

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

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

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

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

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

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

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

Prime演算法的基本思想。

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

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

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

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

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

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

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

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

求解最小生成樹。

方法如下：

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

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

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

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

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

在給定的無向連通性圖中，g = v， e）， （u， v） 表示連線頂點 u 和頂點 v 的邊，w（u， v） 表示該邊的權重;如果 t 的子集為 e，則 g'=v ， t） 是 g 的生成樹，使得 w（t） 是最小的，那麼 t 是 g 的最小生成樹。

最小生成樹實際上是最小權重生成樹的縮寫。

要在n個城市構建乙個通訊網路，需要將n-1條通訊線路排列成乙個集群來連線這n個城市，並考慮如何以最低的成本構建這個通訊網路？

因此，可以引入連通性圖來解決上述問題，n個城市是圖上的n個頂點，然後，邊代表兩個城市的通訊線路，每條邊上的權重就是建設這條線所需的成本，所以現在有n個頂點的連通網路可以建立不同的生成樹， 每個生成樹都可以作為乙個通訊網路，當我們構建這個連線網路時，成本是最小的，連線網路的生成樹稱為最小生成樹。

g （v，e） 是加權連線無向圖，u 是頂點集 v 的非空子集，如果 （u，v） 是權重最小的邊，其中 u u， v v-u，則必須有乙個包含邊 （u，v） 的最小生成樹。

演算法流程：加權連通性無向特許權圖 g （v，e）。

演算法流程：加權連線無向圖 g （v，e） 和 kruskal 為按重量公升序排列選擇適當的邊緣以構造最小生成樹。

最小生成樹

PRIM 演算法。

Kruskal 演算法。

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

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

迴圈不變數：鍵畝。

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

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

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

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

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

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

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

最小生成樹不能有迴圈。

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

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

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

Kruczcard演算法的執行步驟：

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

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

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

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

最小生成樹的實際應用示例如下：

Kruskal 演算法，過程描述：始終以邊緣為優勢位置，首先選擇權重最小的邊緣，始終選擇當前可用的最小權重邊緣，並判斷兩點是否每次都間接連線，如果它們已經間接連線，則跳過此邊緣。 時間複雜度為o（n*logn），適用於求邊緣稀疏連線網路的最小生成樹。

PRIM演算法，過程描述：PRIM演算法總是以頂點為主，起點的選擇是任意的。 從起點到其他點選擇權重最小的邊，然後在該邊的兩個頂點中的每乙個點處找到權重最小的邊，並跳過同樣間接連線的邊。

時間複雜度為o（n2），適用於求邊緣密集連線網路的最小生成樹。

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

最小生成樹屬性和演算法的簡要說明：

最小生成樹屬性：設 g=（v，e） 是乙個連線網路，並且您是頂點集 v 的非空真子集。 如果 （u，v） 是“g 中的點”，則 u 中的端點彎曲（例如 . .

u u），另乙個端點不在 u 中的邊（例如，v v-u），並且 （u，v） 具有最小的權重，則必須有乙個包含該邊 （u，v） 的最小生成樹 g。

集合 U 中的頂點被視為紅色頂點，v-u 中的頂點被視為藍色頂點，連線紅點和藍點的邊被視為紫色邊，權重最小的紫色邊稱為淺邊（即權重最輕的邊）。 因此，MST 屬性中描述的邊 （u，v） 可以縮短為淺色邊。

求MST的一般演算法可以描述如下：對於圖g，從空樹t開始，選擇n-1個安全邊（u，v）並逐個新增到集合t中，最後生成乙個有n-1個邊的MST。

Kruskal 演算法簡介：假設 wn=（v，） 是乙個有 n 個頂點的連線網路，那麼根據 Kruskal 演算法構造最小生成樹並攪拌的過程如下：首先構造乙個只有 n 個頂點和空邊集的子圖，如果將子圖中的頂點視為每棵樹上的根節點， 那麼它是包含 n 棵樹的森林。