希賽教育計算機專業考研專業課輔導招生
希賽教育計算機專業考研專業課輔導視頻
希賽教育計算機考研專業課在線測試系統
普裡姆算法從另一個角度構造連通網的最小生成樹它的基本思想是首先選取圖中任意一個頂點v作為生成樹的根之後繼續往生成樹中添加頂點w則在頂點w和頂點v之間必須有邊且該邊上的權值應在所有和v相鄰接的邊中屬最小在一般情況下假設圖G=(VE) 中已落在生成樹上的頂點集為U則尚未落在生成樹上的頂點集為VU則從 (VU) 頂點集中選取加入生成樹的頂點w應滿足下列條件它和生成樹上的頂點之間的邊上的權值是在聯接這兩類頂點的所有邊中權值屬最小
假設首先選頂點a作為生成樹的根則此時只有頂點a在生成樹中其余頂點bcdefg均不在生成樹上聯接這兩類頂點的邊只有(ab)(af) 和 (ag)其中以邊 (ab) 的權值為最小由此應該選擇邊 (ab) 將頂點b加入到生成樹中之後鏈接 {ab} 和 {cdefg} 這兩個頂點集的邊除了原有的(af)(ag) 之外又增加了 (bc) 和 (bg)在這四條邊中權值最小的邊為(bc)(權值=)自然應選邊 (bc)即將頂點c加入到生成樹中之後應在鏈接頂點集 {abc} 和 {defg} 的邊集 {(af)(ag)(bg)(cd)} 中選擇權值最小的邊(ag)……依次類推直至所有頂點都落到生成樹上為止上述構築生成樹的過程如演示所示（過程中藍色的邊為待選邊紅色的邊為選中的邊）
From:http://tw.wingwit.com/Article/program/sjjg/201311/22856.html
