Re: [問題] 在O(|V|)的時間內找到non-cut點
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/07/31 06:42)推噓5(5推 0噓 11→)留言16則, 4人參與討論串3/7 (看更多)
※ 引述《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
推
07/31 07:40, , 1F
07/31 07:40, 1F
→
07/31 07:42, , 2F
07/31 07:42, 2F
→
07/31 07:43, , 3F
07/31 07:43, 3F
推
07/31 11:39, , 4F
07/31 11:39, 4F
→
07/31 11:39, , 5F
07/31 11:39, 5F
→
07/31 11:40, , 6F
07/31 11:40, 6F
推
07/31 11:42, , 7F
07/31 11:42, 7F
推
07/31 11:44, , 8F
07/31 11:44, 8F
→
07/31 11:44, , 9F
07/31 11:44, 9F
→
07/31 11:45, , 10F
07/31 11:45, 10F
→
07/31 13:59, , 11F
07/31 13:59, 11F
→
07/31 13:59, , 12F
07/31 13:59, 12F
→
07/31 14:42, , 13F
07/31 14:42, 13F
推
07/31 19:06, , 14F
07/31 19:06, 14F
→
07/31 19:06, , 15F
07/31 19:06, 15F
→
07/31 19:08, , 16F
07/31 19:08, 16F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 7 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
