OJ Board

given the description of a graph how can we check efficiently if a particular edge is a BRIDGE ?

hint: DFS

thank you very much Abishek. but i know about the DFS approach. I also use set union and disjoint set algo for this. but i was looking for something faster ... particularly for implementing Fleury's algorithm.

M A Hassan wrote:thank you very much Abishek. but i know about the DFS approach. I also use set union and disjoint set algo for this. but i was looking for something faster ... particularly for implementing Fleury's algorithm.

I don't know how you can search for bridges faster than DFS. Maybe you are looking for the new brach of algorithms called TA (telepathical algorithms)?

Ciao!!!

Claudio

Never once tried the fleury's algorithm myself.
always used to merge disjoint cycles.
any body can help?

abishek wrote:Never once tried the fleury's algorithm myself.
always used to merge disjoint cycles.
any body can help?

Fleury's algorithm is easy to explain, slow to implement.
You start from a vertex and choose an edge that isn't a bridge for the graph.
Then you travel the edge and delete it from the graph.
From every vertex you visit, if there is an edge that isn't a bridge for the reduced graph you choose it, otherwise you may choose bridges. Travel one and delete it.
When you have deleted all edges and are back to the start vertex you have your euler circuit.

Hope this is clear enough, otherwise let me know

Ciao!!!

Claudio

I am clear with the fleury algorithm. But how do I implement the idea of checking whether an edge is a bridge or not in the reduced graph? if I use DFS every time, the order will become n^2.
bye
abi

abishek wrote:I am clear with the fleury algorithm. But how do I implement the idea of checking whether an edge is a bridge or not in the reduced graph? if I use DFS every time, the order will become n^2.
bye
abi

Indeed, fleury's algorithm is inefficient and I'm not aware of any shortcut that allows to skip (or reduces the complexity of) the DFS search for bridges in the reduced graph.

Ciao!!!

Claudio

Hi,
Here is an O(E) algo to find bridges,
first we define low as follows:

low=min(d,min(low[x] | x is a child of w),min(d[x] | E(u,x) is a back edge);

you can calculate low with a recursive function just like DFS with O(E),
then check for every vertex if its low==d.
and an edge is a bridge if and only if low==d;

*back edge is an edge that is not in DFS tree but it connects a vertex to its ancestors.

thats only to find it once right?

how do you modify this to implement fleury's algorithm?

bye
abi