推 yoco315:關鍵字 "union-find algo" kerker 12/30 18:36
> -------------------------------------------------------------------------- <
作者: nikeasyanzi (nikeasyanzi) 看板: C_and_CPP
標題: Re: [問題] 判斷MST(最小擴張樹)是否有cycle
時間: Wed Dec 30 09:53:57 2009
※ 引述《l314520 (一生一世我愛你)》之銘言：
: 遇到的問題： (題意請描述清楚)
: 如何判斷MST(using Kruskal's Algorithm)是否在建立的時候型成cycle呢?
: 希望得到的正確結果：
: 嗯...我想知道怎樣判斷，就這樣...
: 程式跑出來的錯誤結果：
: 本來我用很簡單的方法，三角型ABC
: A
: B C
: 若A-B 30，A-C 40，B-C 50
: 則按照順序建應該是
: A與B都尚未被拜訪過，因此 A-B 30
: 僅A被拜訪過B則無，因此 A-C 40
: 遇到B-C 50的時候，因為B與C都已被拜訪過，因此型成cycle
: 不過剛才發現這是錯的判斷法
: A B
: C D
: 假設AC是10，BD是15，AB是20，CD是25
: AC 10
: BD 15 以上沒問題
: 此時AB兩點皆被拜訪過，則按照三角型推出來的判斷法失敗
: 理論上應該要AB 20
: 開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux)
: winxp codeblock
: 有問題的code： (請善用置底文標色功能)
: 嗯...還在思考階段，沒有code...
: 補充說明：
: none
: 感謝各位
kruskal 的方法應該是每次挑選最小的邊
所以你應該可以這樣做
1.挑選最小的邊 的點 加入一個集合內
2.重複1. 並偵測cycle
偵測cycle的部份就是去看說欲加入的點是不是已經在集合內了
如果邊的兩點都在集合內 那就是形成cycle拉XD
3.直到所有邊都挑完
例子 a
/ \
b___c 假設 a-b 50 ,b-c 40, a-c20
一開始先挑到a-c(weight最小的) 集合內加入a.c兩點
接下挑到b-c 集合變成{a,b,c}
接下來挑到a-b 發現a.b兩點 已經在集合內 所以形成cycle 捨棄...
希望有幫助到你:)
--
CyberPanel 5000CP 換 NT.500
http://myurl.com.tw/05bd
EmailCash 5000e 換 NT.500
http://myurl.com.tw/rgdq
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.137.134.49
→ nikeasyanzi:集合內的元素就把它丟到陣列囉 12/30 09:55
→ nikeasyanzi:每次在去看陣列內有沒有符合的兩個端點 12/30 09:55
推 ledia:那如果放進去的是 a-b, c-d 兩條邊呢 ? :p 12/30 09:57
→ ledia:這應該是用 disjoin set 12/30 09:57
推 walm20:推樓上的disjoint set 12/30 13:54
> -------------------------------------------------------------------------- <
作者: l314520 (一生一世我愛你) 看板: C_and_CPP
標題: Re: [問題] 判斷MST(最小擴張樹)是否有cycle
時間: Wed Dec 30 10:05:54 2009
43
剛才問同學，得到一樣的解答
現在正在想辦法實做
想到一個方法，使用adjancency linked list
假如說共有ABCDE五個點
簡單測資，BC，DE，AC
A A A→C→B
B→C B→C B→C→A
C→B C→B C→B→A
D D→E D→E
E E→D E→D
ps.第三個圖的順序是黃 紅 綠
不過要implement感覺有些複雜...
不知道這樣做是否OK?
還是把問題複雜化了?
感感謝您的解答
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.227.193.166
※ 編輯: l314520 來自: 61.227.193.166 (12/30 10:06)
> -------------------------------------------------------------------------- <
作者: cismjmgoshr (--？？？--) 看板: C_and_CPP
標題: Re: [問題] 判斷MST(最小擴張樹)是否有cycle
時間: Wed Dec 30 10:47:02 2009
原文恕刪
※ 引述《l314520 (一生一世我愛你)》之銘言：
: A B
: C D
: 假設AC是10，BD是15，AB是20，CD是25
拿這個當例子試試看好了
(1)宣告一個陣列，記錄每個點是不是有被連起來
初始值都設為0，代表末連上
(2)
Kruskal's Algorithm:
2.1 選AC這個邊，A和C都標上1
2.2 選BD這個邊，B和D都標上2
2.3 選AB這個邊；雖然A和B的值都不是0，但數字不一樣，所以AB這個邊還是要選。
順便把B和D的值改成1
2.4 由於全部的點都被連起來了，MST建立完成
更一般化的形式:
(1) 宣告一個陣列 Visited[N] = {0}; 一個數字 set = 1;
(2) Kruskal's Algorithm:
2.1 選擇最短的邊 Vi-Vj
2.2 比較 Visited[i] 和 Visited[j] 的值
2.2.1 如果兩個都是零，將兩者都設為一個沒有用過的數字
( Ex: Visited[i] = Visited[j] = set; set++ )
2.2.2 如果只有一個是零，將數值為零的那個設為與另一個相等
( Ex: If Visited[i]==0, Visited[j]!=0 → visited[i]=Visited[j])
2.2.3 如果兩者皆不為零，且兩者值不相等，則掃瞄一次陣列，將與其中之一相
同的數字都改成另一個數字
( Ex: Visited[i]=2 ,Visited[j]=3 → 掃瞄一次陣列，將Visited陣列
中的3都改成2 )
2.2.4 如果兩都皆不為零，且兩者值相等，則不做任何變動。
( 加入此邊會產成迴圈 )
2.3重覆2.2的步驟，直到所有的點都被連起來
2.2.1、2.2.2、2.2.3都是代表合規定的邊，只有2.2.4的邊會造成迴圈
Time complexity: O( ElogE + V^2 )
--
∫work dt = success
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.219.143
推 ledia:O(ElogE + EV) 12/30 10:50
推 l314520:好方法!我沒想到呢 感謝您 12/30 14:27
推 l314520:歷經一番波折，總算搞定MST了，再次感謝 12/30 15:25
> -------------------------------------------------------------------------- <
作者: suhorng ( ) 看板: C_and_CPP
標題: Re: [問題] 判斷MST(最小擴張樹)是否有cycle
時間: Fri Jan 1 09:42:50 2010
推 ledia 大大的連結 ~~
推 ledia:O(ElogE + EV)12/30 10:50
是說第一個時間複雜度的意思是說，先對邊排序，
然後每一次加入邊時， DFS 一次檢查是否產生 cycle (否則是一棵樹)，
共加入 E 條邊，每次要做 DFS 的複雜度是 O(V)，總共就是O(ElgE + EV)
但是我們也可以這樣想：
Kruskal's 事實上，是慢慢將許多森林慢慢合併成一棵樹。
一開始時，每個頂點都自成一棵樹(一個邊、點的集合)，
接下來我們依次嘗試將最小的邊來合併兩棵樹。
如果這條邊連接的是兩棵樹(即，這條邊所連接的兩個頂點分屬不同的集合)
那我們就用這條邊把兩棵樹接在一起(合併兩個集合)，否則忽略這條邊。
-----
DJWS大大的網站 : http://www.csie.ntnu.edu.tw/~u91029/
當中關於 Disjoint Sets： http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html
Disjoint Sets 這種資料結構是用來表示許多兩兩交集為空集合的集合們
最常用的操作就有：union合併兩個集合、find察找詢問的元素屬於哪個集合、
split把一個元素從一個集合中分離出來。在實做 Kruskal's 時我們只會用到
union & find 這兩種操作。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.100.174