作者koalahong ()
看板Programming
标题Re: [问题] kruska的minimum spanning tree问题
时间Tue Jan 30 15:18:10 2007
※ 引述《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