Re: [問題] 想請問一個graph的寫法
※ 引述《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
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 5 篇)：
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
