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

[zanyking (遙遠的旅人)]

※ 引述《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 等等函式要放哪裡?


應該叫『Kruskal』。

我看到你的Vertex定義的是X Y座標，你的問題該不會是
Euclidean Space Traveling Salesman Problem吧？

看起來似乎是打算用MST取Approximation Solution的樣子。

你的Edge一開始存在嗎？還是Vertex間X,Y去算？這差很多喔。






--

JAVA 是一個靜態型別reference指定、強物件型別判定的語言。

屬於類C/C++族。

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 210.85.116.116
推 bigbite:我猜edge的weight就是兩點間的distance
→ bigbite:啊...我在說啥 XDD