A bridge (critical edge) in an undirected graph is an edge whose removal increases the number of connected components.

I need to determine all critical edges in an undirected graph, in $O(V+E)$ time. From what I found out, I need to use a modified DF search, but all pseudo-code algorithms I found have low[v] and d[v] which I don't understand.

Can someone please explain to me the $O(V+E)$ bridge determination algorithm?


closed as unclear what you're asking by Juho, Evil, vonbrand, Kyle Jones, rphv Dec 23 '15 at 0:09

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    $\begingroup$ what is low[v], what is d[v]? how do you expect us to guess what was the purpose of this symbols? Finally did you look at wiki's page: en.wikipedia.org/wiki/…. $\endgroup$ – user742 Apr 11 '13 at 14:22
  • $\begingroup$ Yes, I looked. But I did not understand the algorithm on wikipedia. I mentioned low[v] and d[v] because I noticed these notations in a few bridge determination algorithms. I don't know what they mean. I was hoping someone could explain a bridge determination algorithm. $\endgroup$ – user7681 Apr 11 '13 at 14:56
  • 1
    $\begingroup$ OK, you can show a sample algorithm that you couldn't understand it. $\endgroup$ – user742 Apr 11 '13 at 15:02
  • $\begingroup$ @SaeedAmiri 'code' dfs(G,v) { d[v] = time, time = time +1, low[v] = d[v], for each (v, u) in E, if(d[u] not defined) dfs(G,v), low[v] = min(low[v],low[u]), if(low[u] > d[v]), (v,u) is bridge, else, if u != parent of v, low[v] = min(low[v], d[u]) $\endgroup$ – user7681 Apr 11 '13 at 15:14
  • 4
    $\begingroup$ Edit your question and put your code there in good format. we will edit it as soon as you put the code, but in all if you cannot understand some code is better to ask it in codereview.stackexchange.com, but if you don't understand the algorithm, say which part is hard and may be we can help you. $\endgroup$ – user742 Apr 11 '13 at 17:05