基于堆的無向帶權圖最小生成樹的ＰＲＩＭ方法
2007-12-29 00:00:00李國奇
智能計算機與應用 2007年6期
摘要：通過引用堆的思想。達到了在選最小邊時能充分使用原有比較信息的目的，對PRIM算法進行了探討。
關鍵詞：無向帶權圖 最小生成樹 堆
中圖分類號：TP311.12
文獻標識碼：A 文章編號：1002-2422(2007)06-0061-02
1 傳統PRIM算法原理和實現過程
1.1 PRIM算法的原理
設G=(V，E)是一個連通網絡，U是頂點集V的一個真子集。若(u，v)是G中所有的一個端點在u中、另一個端點不在U里的邊中，具有最小權值的一條邊，則一定存在G的一棵最小生成樹包括此邊(u，v)。
