CreativeAss's blog

Graph-Bridges
By CreativeAss, history, 6 years ago, In English

How to handle parallel edges while finding bridges?

I know one way that count occurrence of each edge. After taking input if occurrence of an edge is greater than 1 don't consider it. (As it will never be a bridge).

I wanted to know some other way.

Thank you very much in advance :) Happy Coding

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I'm pretty sure that you actually don't handle this case in a special way. The normal algorithm (DFS) will move back to the parent if there is a parallel edge, and therefore will determine that these edges cannot be bridges.

But obviously something like if (next == p) continue; in the DFS will not longer work. You can fix this by enumerating the edges and check if you if the next edge is equal to the edge that you came from.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have met a problem that involves multiple edges while using tarjan's algorithm to find bridges within some graph. (156D - Улики).

I remember that I have assigned a flag to each edge to indicate whether it has been used or not. In the original tarjan's algorithm, if the next node has been visited, we should implement updating as long as this "next" node is not the "parent" node. Thus, when multiple edges are involved, even if the "next" node has been visited and is just the "parent" node, we should still implement updating if this edge has not been used. The reason is that we move from parent node to the current node with edge e1, but move back to parent node (just the "next" node) with edge e2 (multiple edges), and thus we implement updating to indicate that e1 is not a bridge.

→ Reply