最小生成樹貪心演算法

㈠ 圖的最小生成樹演算法

圖的生成樹和最小生成樹生成樹(SpanningTree):如果一個圖的子圖是一個包含圖所有節點的樹,那這個子圖就稱為生成樹.

㈡ 利用Prim（普里姆）演算法 構造最小生成樹 程序

演算法同樣是解決最小生成樹的問題。

其演算法為：在這n個點中的相通的邊進行排序，然後不斷地將邊添加到集合中（體現了貪心的演算法特點），在並入集合之前，必須檢查一下這兩點是不是在一個集合當中，這就用到了並查集的知識。直到邊的集合達到了n-1個。

與prim演算法的不同：prim演算法為單源不斷尋找連接的最短邊，向外擴展，即單樹形成森林。而Kruskal演算法則是不斷尋找最短邊然後不斷將集合合並，即多樹形成森林。

復雜度的不同：prim演算法的復雜度是O(n^2),其中n為點的個數。Kruskal演算法的復雜度是O(e*loge)，其中e為邊的個數。兩者各有優劣，在不同的情況下選擇不同的演算法。

Prim演算法用於求無向圖的最小生成樹

設圖G =（V，E），其生成樹的頂點集合為U。

①、把v0放入U。

②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。

③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。

其演算法的時間復雜度為O(n^2)

Prim演算法實現：

（1）集合：設置一個數組set(i=0,1,..,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1）

（2）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
{先選定一個點，然後從該點出發，與該點相連的點取權值最小者歸入集合，然後再比較在集合中的兩點與其它各點的邊的權值最小者，再次進入集合，一直到將所有的點都歸入集合為止。}

㈢ prim和kruscal演算法得到的最小生成樹是否一樣

應該不一樣。可以用一個圖根據兩演算法試一下，若一樣，再修改圖，之後應該就可以了。
（網路或者查書本更加有效……）
構造G的最小生成樹的Prim演算法的基本思想是：首先置S={1}，然後，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且c[i][j]最小的邊，將頂點j添加到S中。
這個過程一直進行到S=V時為止。
Kruskal演算法構造G的最小生成樹：將所有的邊按權從小到大排序。然後從第一條邊開始，依邊權遞增的順序查看每一條邊，並按下述方法連接2個不同的連通分支：當查看到第k條邊(v, w)時，如果端點v和w分別是當前2個不同的連通分支T1和T2中的頂點時，就用邊(v, w)將T1和T2連接成一個連通分支，然後繼續查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看第k+1條邊。這個過程一直進行到只剩下一個連通分支時為止

㈣ 試設計解決tsp問題的貪心演算法，分析時間復雜度，試分析是否存在o的有效演算法5分

貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心演算法不是對所有問題都能得咐遲禪到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最旦蠢優解或者是整體最優解的近似解。

比如最小生成樹Kruskal演算法，每次在不構成環的前衡塵提下，總是選擇權最小的邊。
找零錢問題：以人民幣1元，2元，5元，10元，20元，50元，100元為例，要求所找的張數最少 背包問題：假設物體重量W1，W2．．．Wn其對應的價值為P1，P2．．．Pn，物體可分割，求裝入重量限制為m的背包中的物體價值最大．

㈤ 最短路演算法和最小生成樹演算法有什麼區別

兩個演算法沒有什麼太多的聯系，只能說是想法類似，都用了一定程度的貪心思維。
最短路是要求一點到另外的點的最短路徑，只要最短的長度到達就好，除了出發點和終點外一概不管。如果不求一點到所有點的最短路，甚至可以不管所有點是否都聯通。
最小生成樹則要保證第一所有點都是聯通的，不然就稱不上是樹了，而後保證樹的邊長度之和最小。

㈥ 基礎-11：最小生成樹（MST）

最小生成樹（minimum spanning tree）是圖計算中基本的問題，背後的問題非常直接，假設無向連通圖G(V, E)，且E中的每條邊e有權值（可以表示距離、價值等），找嘩和出一顆樹，連接G中所有的邊，且連接這棵樹的所有邊的權值之和最小。在電子製造中，如何以最低的成本連接多個針管便是這一問題。

下面以一個圖來對此進行說明：

前面兩課中介紹了動態規劃和貪心演算法，都是用來解決最值問題，本文中的最小生成樹很顯然也屬於此類。最小生成樹使用貪心演算法，文中會對貪心演算法的使用進行說明。

假設mst是最終要求的最小生成樹，若A是最小生成樹mst邊集的子集，如果每次選擇一條邊(u, v)加入A，並且確保A始終是mst邊集的子集，則最終得到的A必然是mst最小生成樹的邊集。這樣的邊(u, v)稱為A的 安全邊 。安全邊即為可以選擇的邊。

為了得到安全邊，下面介紹一些概念。無向圖G=(V,E)的一個切割(S, V-S)是節點集V的一個劃分，如圖2所示：

顯然，一個切割將圖劃分為兩部分。如果一條邊(u,v)，u在S中，v在S-V中，則稱邊(u,v)橫跨切割(S, V-S)。如果集合A中不存在橫跨該切割的亂手盯邊，則稱該切割尊重A；在橫跨切割的所有邊中，權重最小的邊稱為輕量級邊（註：輕量級邊可能不是唯一的）。

下面的定理和推論保證了Kruskal和Prim演算法的正確性，感興趣的童鞋可以自己證明或參考演算法導論中的說明。

根據定理1和推論1，構造最小生成樹可以有兩種方式，一種是切割的角度，一種是森林的角度。切割的角度：先從圖中選取一個點n ₁ ，劃一個切割({n ₁ }, V-{n ₁ })，然後找這個切割的輕量級邊以及這個邊在 V-{n ₁ }的節點n ₂ ；然後再劃一個切割（{n ₁ , n ₂ }, V-{n ₁ , n ₂ })，再找出對應的輕量級邊，薯困...,直到所有的節點，每一步中找到的輕量級邊組成的集合為最小生成樹中的邊。

森林的方式是：首先將每個節點都看成一個連通分量（此時有n個連通分量），尋找連通連接連通分量權值最小的邊(u, v)，(u, v)連接的連通分量為C ₁ 和C ₂ ，則(u, v)連接後，合成一個更大的連通分量C ₁₂ （此時有n-1個連通分量）；然後對n-1個連通分量繼續實施上述類似的動作，直至最後變成一個連通分量。

切割的角度對應的是Prim演算法，森林的方式對應的是Kruskal演算法，演算法本身都很簡單，在此不再贅述，下面兩組從演算法導論中摘取的圖很好地解釋了對應的演算法。

最小生成樹是圖計算中的基本演算法，理解演算法的關鍵是切割基礎上的輕量級邊，上文的說明中野間接解釋了利用貪心演算法的正確性，相對而言，最小生成樹是較為簡單和基礎的演算法，是其他演算法的基礎。