作者zanyking (遥远的旅人)
站内Programming
标题Re: [问题] kruska的minimum spanning tree问题
时间Fri Feb 2 02:42:16 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 等等函式要放哪里?
应该叫『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
1F：推 bigbite:我猜edge的weight就是两点间的distance140.113.138.113 02/02 02:54
2F：→ bigbite:啊...我在说啥 XDD140.113.138.113 02/02 02:54