promotion image of download ymail app
Promoted
asked in 電腦與網際網路程式設計 · 1 decade ago

有誰可以幫我說明 prims 演算法(虛擬碼) 在幹麻嗎??

T={};

TV={0};

while(T coutains fewer than n-1 edges)

{

let (u,v) be a least cost edge such that u TV and v TV;

if(there is no such edge)

break;

add v to TV;

add (u,v) to T;

}

If(T contains fewer than n-1 edges)

printf(“No spanning tree\n”);

-----------------------------------------------------------------------

幫我說解釋一下啥意思吧!!!

那如果要把它寫成c語言,要怎麼寫呢??

謝謝囉!!!(20點)

3 Answers

Rating
  • 1 decade ago
    Favorite Answer

    令一個無方向性的圖形G=(V,E),使G成為一個TREE T,則T稱之為G的spanning tree

    而prims 演算法是要求算出minimal spanning trree的一種演算法(即最小cost)

    T={}; 建立一個線的空集合

    TV={0}; 建立一個點的集合,並以0開始

    while(T coutains fewer than n-1 edges)即未全部點連接好,EX:4個點的圖需3條線相連.因此繼續跑WHILE廻圈

    {

    let (u,v) be a least cost edge such that u TV and v TV;

    //在上一行裡.她會去找點集合TV裡的每一點能連到的其它不在點集合裡的線.並找出最短路徑.並取之

    if(there is no such edge) //代表非連接圖,即代表這個graph無法走完全部點(ex:a,b,c,d,e相連..但f僅一個點在那.並未連接至任何一點..)

    break; //代表無法轉成tree..所以break

    add v to TV; //將點記至點集合TV中

    add (u,v) to T; //將線記在線集合T中

    }

    If(T contains fewer than n-1 edges) //即未連接好,spanning tree無法完成

    printf(“No spanning tree\n”);

    2006-01-08 15:47:18 補充:

    還有另一方法為Kruskal'S 演算法

    • Commenter avatarLogin to reply the answers
  • 1 decade ago

    權值沒有相同,則唯一喔

    • Commenter avatarLogin to reply the answers
  • 1 decade ago

    用Prim求出的解不是唯一的嗎?是不是唯一的呀?還是有很多種可能…因為我解過一題有許多種答案耶…

    • Commenter avatarLogin to reply the answers
Still have questions? Get your answers by asking now.