Re: [問題] 判斷MST(最小擴張樹)是否有cycle
推 ledia 大大的連結 ~~
推
12/30 10:50,
12/30 10:50
推
12/30 10:54,
12/30 10:54
是說第一個時間複雜度的意思是說，先對邊排序，
然後每一次加入邊時， 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
→
01/01 13:20, , 1F
01/01 13:20, 1F
→
01/01 13:20, , 2F
01/01 13:20, 2F
→
01/01 13:20, , 3F
01/01 13:20, 3F
→
01/01 13:20, , 4F
01/01 13:20, 4F
推
01/01 21:26, , 5F
01/01 21:26, 5F
→
01/01 21:26, , 6F
01/01 21:26, 6F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 5 篇)：