作者peropero1 (呜呜~~~~)
看板Grad-ProbAsk
标题[理工][软体]99台大软体设计
时间Sat Dec 11 21:23:55 2010
第5题
Give a pseudocode that determines whether or not an undirected graph
G=(V,E) contains a cycle. You need to show that your pseudocode runs
in O(V) time. You may assue that the adjacency-list representation
of G is given, and for each vertex u in V, Adj[u] consists of all the
vertices adjacent to u in G.
题目要求演算法需在O(V)内完成
想请问一下版上大大该怎麽做??
(是否可直接用DFS求解??其复杂度为Θ(V+E))
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.126.0.166
1F:推 tureday:用DFS做,没回圈,点会比边多,有回圈,用的点边一样多.O(V) 12/12 02:14
2F:推 skill91002:请问楼上是用DFS找back edge的找法吗? 12/12 09:17
3F:→ peropero1:可以请问一下有回圈跟没回圈的差异吗??? 12/12 15:58
4F:推 christianSK:没有回圈的话 |E|<=|V|-1 O(E) = O(V) 12/12 16:05
5F:→ christianSK:有回圈的话 O(E) = O(V^2) 在worst case下 12/12 16:05
6F:→ christianSK:我也想知道一楼 怎麽在有回圈下可以用O(V) 完成 12/12 16:06
7F:→ christianSK:我刚刚说的好像是要连通才是@@ 12/12 16:07
8F:→ peropero1:话说…题目只说是undirect…并没有说是简单图或多重图 12/12 16:41
9F:→ peropero1:所以我想worst cast应该不只O(V^2) ??? 12/12 16:41
※ 编辑: peropero1 来自: 59.126.0.166 (12/12 16:42)
10F:→ peropero1:毕竟Kn似乎看来不是worst case... 12/12 16:43
11F:推 tureday:只要判断有回圈就OUTPUT有回圈,Kn也不用所有回圈都找过 12/13 18:25
12F:推 tureday:所以有回圈的话,所搜寻过的点和边会一样 12/13 18:27
13F:→ tureday:设一个v的前行点u,w是由v出发连到的点,DFS做到前方没有没 12/13 18:52
14F:→ tureday:找过的点就会backtracking,这时候如果有w=/=u就有回圈 12/13 18:55