Re: 有關Kruskal演算法語法的問題

看板C_and_CPP (C/C++)作者ledia (contemplation)時間18年前 (2006/03/23 13:16)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串1/2 (看更多)

※ 引述《huangwh (香腸)》之銘言： : 你是說 3的媽媽為2 : 2的媽媽為1 : 最後 1 的媽媽就是6 : 也就是(6,1) : 是這樣子嗎? : 方便用我原本的例子 : 來講解一下可以嗎? : 謝謝 : 但是我就是不知道要怎將這斷語法用c++寫出來~!! 不考慮效率什麼的問題的話最簡單的方法就是: 假設你有七個點好了那就 maintain 7 個 circular link list 初始值就是大家指著自己０┐ １┐ ２┐ ３┐ ４┐ ５┐ ６┐ ↑│ ↑│ ↑│ ↑│ ↑│ ↑│ ↑│ └┘ └┘ └┘ └┘ └┘ └┘ └┘ next operation 有分兩類, 一個是把 (x, y) 歸成同一類這裡稱之為 Union(x,y) 一個是查 (x, y) 是否為同一類這裡稱之為 isSameGroup(x,y) 每次先查查他們在不在同一個 group (用 isSameGroup(x,y)) 如果已經在同一個 group 了, 就 ignore, 就是你 * 的那類否則就用 Union(x,y) 把他們組合起來 (5,0) 把 5 拿出來, 它現在是: 順著它的 next link 往下走５┐ 直到走回自己都沒有看到 0 ↑│ 所以 isSameGroup(5,0) 就是 false └┘ 我們就要進行 Union(5,0) 的動作 ┌─┐ │ ↓ ０５１┐ ２┐ ３┐ ４┐ ６┐ ↑ │ ↑│ ↑│ ↑│ ↑│ ↑│ └─┘ └┘ └┘ └┘ └┘ └┘ (3,2) 把 3 拿出來, 它現在是: 順著它的 next link 往下走３┐ 直到走回自己都沒有看到 2 ↑│ 所以 isSameGroup(3,2) 就是 false └┘ 我們就要進行 Union(3,2) 的動作 ┌─┐ ┌─┐ │ ↓ │ ↓ ０５２３１┐ ４┐ ６┐ ↑ │ ↑ │ ↑│ ↑│ ↑│ └─┘ └─┘ └┘ └┘ └┘ (6,1) 把 6 拿出來, 它現在是: 順著它的 next link 往下走６┐ 直到走回自己都沒有看到 1 ↑│ 所以 isSameGroup(6,1) 就是 false └┘ 我們就要進行 Union(6,1) 的動作 ┌─┐ ┌─┐ ┌─┐ │ ↓ │ ↓ │ ↓ ０５２３１６４┐ ↑ │ ↑ │ ↑ │ ↑│ └─┘ └─┘ └─┘ └┘ (2,1) 把 2 拿出來, 它現在是: 　┌─┐ │ ↓ 順著它的 next link 往下走２　３直到走回自己都沒有看到 1 ↑　│ 所以 isSameGroup(2,1) 就是 false └─┘ 我們就要進行 Union(2,1) 的動作 ┌─┐ ┌─┐ ┌─┐ │ ↓　│ ↓ │ ↓ ２３→１６０５４┐ ↑ │ ↑ │ ↑│ └─────┘ └─┘ └┘ (6,3)* 把 6 拿出來, 它現在是: 　┌─┐ ┌─┐ │ ↓　│ ↓ 順著它的 next link 往下走２　３→１６直到走回自己前遇到了 3 !! ↑ 　│ 所以 isSameGroup(2,1) 就是 ture, ignore (6,3) ! └─────┘ 以下略中間的 link list 處理方法不難, 可以自己想想 :) -- 有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。　存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你　，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也　是比較不容易被擊倒的人。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.56 ※ 編輯: ledia 來自: 140.112.30.56 (03/23 13:48) ※ 編輯: ledia 來自: 140.112.30.56 (03/23 13:48)