Re: [問題] 判斷MST(最小擴張樹)是否有cycle
原文恕刪
※ 引述《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
推
12/30 10:50, , 1F
12/30 10:50, 1F
推
12/30 10:54, , 2F
12/30 10:54, 2F
推
12/30 14:27, , 3F
12/30 14:27, 3F
推
12/30 15:25, , 4F
12/30 15:25, 4F
推
01/03 19:04, , 5F
01/03 19:04, 5F
討論串 (同標題文章)