[問題] 判斷MST(最小擴張樹)是否有cycle
遇到的問題： (題意請描述清楚)
如何判斷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
感謝各位
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.227.193.166
推
12/30 18:36, , 1F
12/30 18:36, 1F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 5 篇)：