作者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