Re: [問題] kruska的minimum spanning tree問題

看板Programming作者koalahong時間18年前 (2007/01/30 15:18)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/3 (看更多)

※ 引述《fatal5566 (致命5566)》之銘言： : 小弟我的疑問不是在演算法的地方 : 而是其中要如何實做disjoint set : graph不是可用 adjacency list來做 : 如果我寫了一個graph的class : c++ code 類似這樣 : class Graph{ : ... : ... : vector<vertex> //存所有點 : }; : class Vertex{ : int x_axis; : int y_axis; : list<Vertex> //每個點的adjacency list : }; : 這樣我要如何用disjoint set? : 做好的minimum spanning tree要怎麼表示? : 如果可以能不能稍微提示一下 : make_set fine_set union 等等函式要放哪裡? 我自己寫過這個algorithm不過不是用disjoint set就是了而且可能因為需求不同，我也不是用x座標和y座標來表示點我只記了邊的資訊譬如點a可以連到點b, c, d距離分別為10, 20, 30之類的訊息也就是你vertex的宣告內不要用list<vertex> 改用list<edge>，edge宣告可能類似下面這樣 struct edge{ int adj; //鄰居 int dis; //距離，讀入資料的時候應該很容易就可以順便算出來 }; 接著對所有的邊做排序(用stl + operator overloading) 再宣告一個陣列紀錄用過的點來防止cycle 跑完algorithm就得到MST了以上是我的實做方式，你可以參考一下應該有更好的才對至於表示的方法，其實沒有很懂你的意思如果是指資料結構的話當然還是Graph囉如果是指output到monitor的話可以印出所有你選到的邊起點、終點、邊長和整個MST的總長度等資訊，只是要驗證的話這樣就很夠了夠強的話就畫圖吧 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.129.164.239