※ 引述《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