作者ephesians (ephesians)
看板Programming
标题Re: [问题] 想请问一个graph的写法
时间Wed Jun 6 22:47:35 2007
※ 引述《GORD (☆杨培安 完美世界☆)》之铭言：
: 我想请问一个graph的演算法
: 就是输入的部份...任意决定现在有几个点
: 然後会自动产生每一个点都可以走的到任意点的graph
: 例如：我输入 5，可能就会产生
: 3
: ／
: 1—5—4
: ＼
: 2
: 资料型态可能就是
: NodeID 连接到的点
: 1 5
: 2 4
: 3 4
: 4 2,3,5
: 5 1,4
: 不晓得有什麽演算法可以用呢?
: 保证可以每一个点都能走到其他的点
只要是树,就符合你所要的图.
最简单的作法是,先随便选一个点当树根,
然後对每个未处理的树节点建立1-k个子节点:
A = 未加入树的点集合
root = oneNodeOf(A) // use some method to select a node
A = A - root
current = root // a cursor
while (|A| > 0) {
times = (int)(rand() % k + 1); // C code
if (times > |A|) times = |A|
for (i=1; i<=times; i++) {
child = onNodeOf(A)
link(current, child)
A = A - child
}
current = nextNodeOf(current) // Go to next node in width first order
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.160.111.29