---

---

遇到的問題： (題意請描述清楚)

如何判斷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

> -------------------------------------------------------------------------- <

---

※ 引述《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

> -------------------------------------------------------------------------- <

---

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)

> -------------------------------------------------------------------------- <

---

原文恕刪

※ 引述《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 大大的連結 ~~


是說第一個時間複雜度的意思是說，先對邊排序，

然後每一次加入邊時， 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

--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:43:20