作者Leon (Achilles)
站內Prob_Solve
標題Re: [問題] 在O(|V|)的時間內找到non-cut點
時間Wed Jul 31 06:42:50 2013
※ 引述《Leon (Achilles)》之銘言：
: 標題: Re: [問題] 在O(|V|)的時間內找到non-cut點
: 時間: Wed Jul 31 01:49:38 2013
:
:
※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 76.170.77.110
: 推 seanwu:non-cut point可以不是leaf，例如完全圖上任何一點都是 07/31 02:03
: → Leon:that's correct, however, my algo just want to find one 07/31 02:09
: 推 seanwu:噢! 我誤會了你的意思了，你是指spanning tree嗎? 07/31 02:10
: → Leon:其實, non-cut point is a leaf in one spanning tree 07/31 02:10
: → Leon:看來你了解了, good 07/31 02:11
: → seanwu:哈... 因為你第三行突然冒出"a tree"，一時沒轉過來XD 07/31 02:15
: → seanwu:不過我覺得step 2.應該不是O(K)? 最差可以到 O(K^2) 吧? 07/31 02:16
: → seanwu:如果是需要看過這些edge，把他們挑出來的話 07/31 02:17
: → Leon:這就是巧妙的地方, 你去試一個圖做看看就知道 07/31 03:23
: 推 FRAXIS:我也覺得在第二步的時候會需要O(k^2)的時間 有什麼技巧嘛？ 07/31 04:23
技巧就是說破了不值一毛錢的小東西.
舉個簡單的例子, 4 Node graph, as a ring.
The neighboring matrix is
0 1 0 1 ;
1 0 1 0 ;
0 1 0 1 ;
1 0 1 0 ;
So.. if you start from the first node, you will find neighbors are
V_2 and V_4. In step 1, it takes 2 operations to look at the E_{1,j}.
Then, you modify the neighboring matrix, remove the edges
E_{1,2} -> E_{2,1} and E_{1,4} -> E_{4,1}.
Because we don't need loop in spanning tree.
In step 2, you start to look at node 2,
now it only takes you 1 operation to get V_3
because edge E_{2,1} has been removed in previous step.
Follow this concept, I guess you only need O(|V|).
--
一簫一劍平生意
負盡狂名十五年
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 108.199.165.64
1F：推 rebaudiana:不太懂…如果原圖是N個節點的完全圖，在處理第K個節點 07/31 07:40
2F：→ rebaudiana:感覺會需要做(N-K)個遍歷，這樣總共就是N*(N-K)了 07/31 07:42
3F：→ rebaudiana:還是說有什麼資料結構可以避開對已在佇列裡的點的遍歷? 07/31 07:43
4F：推 FRAXIS:我的疑問是，如果是兩個K5完全圖 中間用一條edge相連 07/31 11:39
5F：→ FRAXIS:起始的節點是完全圖中 不與bridge相接的節點 07/31 11:39
6F：→ FRAXIS:所以你會得到其中的五個頂點 那此時你會移除多少條邊？ 07/31 11:40
7F：推 FRAXIS:是四條? (與起始節點相鄰的邊) 還是十條？ (K5中的邊) 07/31 11:42
8F：推 ledia:移除五條邊和選定的 child node 之外另外四個點 07/31 11:44
9F：→ ledia:演算法應該沒問題, 但我不覺得這樣是 O(|V|) 就是了 07/31 11:44
10F：→ ledia:啊 是移除四條邊和另外三個點, 我不會算術了 XD 07/31 11:45
11F：→ scwg:這個做法要 O(|V|) 可能要圖用 linked list 存adjacency list 07/31 13:59
12F：→ scwg:然後每條邊存逆邊的指標 07/31 13:59
13F：→ scwg:唔, 之前沒看懂, 上面那樣做沒有比較快 07/31 14:42
14F：推 FRAXIS:如果要移除四條邊和另外那三個點 那另外那三個點的邊要 07/31 19:06
15F：→ FRAXIS:不要移除？ 我想應該要的吧..有辦法可以在O(K)之內移除？ 07/31 19:06
16F：→ FRAXIS:喔，抱歉，我發現ledia對時間複雜度有同樣的疑問 07/31 19:08