NO．3最小支撐樹
在上面我們介紹了關節點算法，現在我們來談下另外一個概念，支撐樹。在一個聯通圖G中，某一個能夠連接所有點的無環子圖，則稱作G的一棵支撐 樹或生成樹（spanning tree），如果邊帶有權值，那么生成的支撐樹中所有權值最小樹就是最小支撐樹或者最小生成樹。
聚類分析、網絡架構設計、VLSI布線設計等諸多實際應用問題，都可轉化并描述為最小支 撐樹的構造問題。在這些應用中，邊的權重大多對應于某種可量化的成本，因此作為對應優化問 題的基本模型，掌握最小生成樹算法很重要。
這種問題，暴力是不可取的，時間復雜度太高，那么讓我們一步步分析下。
我們首先假設G＝（V，E）是一個連通網絡，U是頂點集V的一個非空真子集。若（u，v）是G中一條“一個端點在U中（例如：u∈U），另一個端點不在U中的邊（例如：v∈V－U），且（u，v）具有最小權值，則一定存在G的一棵最小生成樹包括此邊（u，v），我們先假設這條邊為安全邊ri。
這樣，我們假設我們要的樹是個只包含一個點的集合即為U，另外的點為V－U，然后我們就把安全邊加入進去，然后更新這兩個集合的數據。依次進行下去直到所有點進入。但是這樣子的時間復雜度還是有點高，我們想一下還有上面優化的方法。怎樣才能減少每次更新的時間呢？我們還有一個強大的助手STL。
STL中的優先隊列提供了快捷的插入和修改，可以極大地優化時間。
下為示例與優化后的代碼：
a＞ 首先選擇A結點作為點集
b＞ 找A－－B，A－－D，A－－G權值最小的點（B），之后將其加入點集中
c＞ 找點集中跨越邊最小的邊，A－－D，A－－G，B－－C，到D的權值最小，將其加入到點集中
d＞ 重復上述過程，A－－G，D－－G，D－－E，B－－C，到G的權值最小，將其加入到點集中
一直重復上述步驟直到找到的邊數為n－1條，i就是通過Prim算法找到的最小生成樹了。
