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