Re: [問題] 判斷MST(最小擴張樹)是否有cycle
※ 引述《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
→
12/30 09:55, , 1F
12/30 09:55, 1F
→
12/30 09:55, , 2F
12/30 09:55, 2F
推
12/30 09:57, , 3F
12/30 09:57, 3F
→
12/30 09:57, , 4F
12/30 09:57, 4F
推
12/30 13:54, , 5F
12/30 13:54, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 5 篇)：