OJ Board

Can anyone tell me how can i find the bridge(s) of a graph G in O(E) time.
Thanks in advance.
Naushad

Use DFS, which is linear, and then check for backedges. If there's no back edges, then it's a bridge.

Dear Larry,
Sorry for late reply. First of all your statement is not clear to me. I need the bridges of the graph. Not if there any bridge or not. Next, if I apply DFS it is O(V+E), but i have the limitation of O(E).
Naushad

Larry is right. You can use a dfs for this. The actual name of this algorithm is finding "biconnected components". It is hard to explain here on the forum, but easy to implement. You will find nice sites about it on google. There is another algorithm for this which doesn't use recursion, but I don't know much about its complexity. I suspect that it's also O(E+V).

The fastest method I know of is also dfs with O(V+E). If you ever find one that runs in O(E) or faster (and I hope you do ) could you post it on this board? Thanks.

Could anyone tell me, what's wrong with my code ?
I post it under this link: http://acm.uva.es/board/viewtopic.php?t=1853

Thanks in advance
DM

Thanks Dominik,

I went to check CLR and sure enough there is supposed to be an O(E) way of finding bridges. But the method that I know of happens to be O(V+E)!

I'll think about this and reply to the board if I can sort it out

I think most of this confusion is stemming from the close relationship between O(V+E) and O(E). For all practical purposes, they're the same, so sometime you'll see O(V+E) referred to as O(E) (which is technically a bit sloppy). The only way in which O(E) can be less than O(V) is if a graph has an asymptotically large number of isolated vertices.

If the input to an algorithm contains some explicit representation of vertices, and assuming the algorithm has to look at all it's input, then said algorithm must be Omega(V). The only case in which you could have an O(E) algorithm instead of an O(V+E) is if the isolated vertices aren't represented explicitly (either the vertices are numbered and all vertices from 1 to V are implicitly present, or a count of isolated vertices is given).

Personally, I think whoever asked you for an O(E) bridge algorithm was just being sloppy, and was actually looking for an O(V+E) algorithm. Isolated vertices have nothing to do with the bridges of a graph, so clearly they are not of interest. Lets assume you have been given the graph as a list of edges, each edge represented by an unordered pairs of integers.
case 1: the vertex indexes (assume a range of 1..V), are dense, that is to say: V is O(E). Then O(E) == O(V+E).
case 2: the vertex indexes are sparse, so their range is asymptotically larger than E. Then you need to do some work to identify edges which meet, e.g. sorting all the vertex indexes present or putting them in a tree, so you're stuck with O(E log E) now.

If you're looking at case 1, the O(E) / O(V+E) distinction is a red herring. If you're in case 2, you won't get an O(E) algorithm anyway. In general, the running time for any graph algorithm which takes a list of edges as input and examines them all is going to be Omega(min(V+E, E log E))

So I think there's some fundamental confusion at the root of this question.

I think you're not right, Christopher. I can put all non-isolated vertices in a queue while reading the input, and then run the dfs only from vertices that are in the queue. The dfs would have complexity O(E+V'), where V' is the size of the queue. V' is also at most two times more than E, so it can actually be O(E). One thing you are right about though: O(E) and O(E+V) are pretty much the same.

Thanks, Christopher and Makbet. It's much clearer now.

I think Christopher is right. Lets look the definition of O notation.

f(x) = O(g(x)) if exists constant c and n0 > 0 such tath f(x) <= c.g(x) for any n >= n0.

Now lets see how many edges exists in a graph. In a complete graph with n vertex there are at most C(n, 2), or n choose 2, edges.

In that way we can see that E = O(V^2).

And for the definition of O notation:

O(V^2) = O(V^2 + V)

so

O(E) = O(E+V).