Determine if edge is a bridge in a graph

Question

I would like to implement Fleury’s algorithm to find Eulerian trails in a graph. This algorithm requires me to tell if a given edge is a cut edge (bridge).

Is there a more effective way of doing this besides the one described here?

Answer 1

The algorithm you link to checks if an edge $uv$ is a bridge in the following way:

1. Do a depth-first search starting from $u$, and count the number of vertices visited.
2. Remove the edge $uv$ and do another depth-first search; again, count the number of vertices visited.
3. Edge $uv$ is a bridge if and only if these counts are different.

Asymptotically, this is probably the best we can do, because depth-first searches are the easiest way to check for bridges. But we can reduce the number of depth-first searches that have to be done.

First, there is absolutely no reason to do two depth-first searches per edge we check. The most straightforward way to check if edge $uv$ is a bridge in $G$ is to do a single depth-first search in $G-uv$, starting at $u$. Rather than count the vertices visited, just check if $v$ is one of them! (We can even stop the search as soon as we find $v$.) This is the biggest improvement; if the DFS part of the algorithm is the majority of the running time, we've just sped things up by a factor of $2$.

A second big shortcut is specific to Fleury's algorithm. Suppose we're currently at vertex $u$ and we've discovered that edge $uv$ is a bridge. That means that (assuming a tour is possible) edge $uv$ must be the last edge we use out of $u$. In particular, assuming a tour is possible, there can be no other bridges out of $u$ - otherwise multiple edges would have to be the last edge we take, which is a contradiction. So we can simplify the iterative step at each vertex to the following:

1. Let $v_1, v_2, \dots, v_k$ be the neighbors of $u$.
2. If $k=1$, use $uv_1$, the only possible edge.
3. Check if $uv_1$ is a bridge. If it's not, use it.
4. If $uv_1$ is a bridge, use the edge $uv_2$ instead. We don't have to do another check on this edge: we know it's not a bridge.

Finally, we can adapt Fleury's algorithm somewhat to a recursive procedure that passes to a subgraph whenever it encounters a bridge. Suppose we've done a depth-first search from vertex $u$ and discovered that $uv$ is a bridge. In that case, we know that the Eulerian trail we want will begin by exploring $u$'s component of $G-uv$, then take edge $uv$, then continue with the rest of the graph.

So when this happens, we can actually remove edge $uv$ from the graph for the moment; recursively call the Eulerian trail procedure to find a tour (of the current component) from $u$; then, print edge $uv$ and continue finding an Eulerian trail from $v$.

Answer 2

I want to suggest another approach to handle bridges in Fleury's algorithm. The strategy is to avoid bridges rather than to detect (and avoid) them. So, this strategy can be used to find a Eulerian trail, but it is not suitable to find all Eulerian trails. I discovered this approach for the bridge algorithm while storm Eunice was raging over Belgium, so I call it Eunice’s algorithm. (Though, I could not verify if this approach is a new approach at all.) Here is my theory about Eunice’s algorithm to avoid bridges:

When we want to find a Eulerian trail in a graph G0 we start in a vertex s and end in a vertex e. For Eulerian cycles s = e. From the moment we do a first step on the trail by walking an edge st we end up in vertex t with a ‘remaining’ graph G1 to walk. In G1 vertices t and e have always an odd degree. Remark that from the first step on, the final vertex e of the trail is determined and cannot change.

We take the point of view that we ended up somewhere in a vertex u with odd degree from a ‘remaining’ graph Gn (with n > 0) and, of course, e is still in Gn. OK, now assume uv is a possible next edge to walk and uv is a bridge. What do we know? Well, we know that walking the bridge would separate the graph in 2 separated graphs, call them H with u in it and H' with v in it. Then we know that e will be together in H' with v. Why? When we (finally and unavoidable) cross the bridge at a certain point during our walk, there is no way back by definition, so the destination e should be on the same side of the bridge as v. From the point of view of vertex u, e is ‘on the other side of the bridge’ uv.

OK, now we can define a distance function d which returns the 'minimum distance' between a vertex and the destination e: The minimum distance is the minimum number of edges that connects a vertex to e. So, trivially d(e) = 0. The adjacent vertices x of e have d(x) = 1. Etc. We will later discuss a distance algorithm more detailed.

Let us see now how we can use the distance to solve the bridge issue. If we are in vertex u and uv is a bridge then we know that e is across the bridge on the side of v and we also know that d(u) = d(v) +1. Further we know that all other adjacent vertices x of u, if any, have d(x) = d(u) + 1. We can convert this knowledge into a criterium to 'avoid' bridges: If you are in vertex u and you are to choose a next edge, choose NOT a vertex with the single lowest distance. In other words: If there is a possible bridge in front of you, it will be the connected vertex with the single lowest distance to e.

Nice. But is this approach expensive? While walking the trail the distances (smallest number of edges to e) can change (increase). So, do we have to recalculate the distances for the remaining vertices by each step we make on the trail? No! Let's see why. If we walk an edge uv, there are 3 possibilities concerning the distance:

• d(u) = d(v) - 1 In this case, u is closer to e than v is. So, we are walking away from e and it is possible that edge uv is part of the shortest path from v to e. When walking the edge uv it is possible that d(v) does not hold anymore. Unless there is another adjacent vertex v' with d(v) = d(v'). In that case u can keep the distance d(u) by using v' on its shortest path to e. So, yes, we must recalculate the distances if d(u) < d(v), unless u has another adjacent vertex v' with d(v) = d(v').

• d(u) = d(v) In this case u and v cannot be involved in each shortest path to e. In other words, taking away uv will not change anything to d(u) or d(v), nor to the distance of adjacent vertices or any other distance at all. So, no, we do NOT have to recalculate distances in this case.

• d(u) = d(v) + 1. In this case v is closer to e than u. Remember that we will only walk this edge if there is no alternative because we will always choose NOT the vertex with the single shortest distance. So, either u has no other adjacent vertices than v (walking uv is bye-bye to u) or the other adjacent vertices of u have the same distance than v, so there are alternative routes for uv to keep the distance d(v) (and the distances of all other involved vertices): Walking the edge uv will NOT force us to recalculate the distance.

To keep it simple, we have only to recalculate the distances when we are moving away from e via the edge uv and uv is uniquely on the shortest track from v to e. When we have to recalculate the distances, do we have to do that for all vertices left in the ‘remaining graph’? No, in fact we have only to recalculate the distances of the vertices that are ‘behind’ (= further away) vertex u. But as we will see, we will build the distance table from close to far and there is not really a bonus for this restriction.

But even if we only have once in a while to recalculate the distances, how difficult is it to do so? Not difficult. We assume we have a adjacency matrix for the vertices available, then the algorithm can be simple as:

• Create a set of all vertices left in the ‘remaining’ graph. Select vertex e and remove e from the initial set. Give the selected vertex distance 0.
• Now repeat recursively until no vertices are left in the set: Increase the distance by 1. Select for each vertex in the previous selection the adjacent vertices. Append them to a new selection, remove them from the set and assign the increased distance to them.

That's all.

I coded the Eunice’s algorithm in an ABAP program for testing. E.g. the input of the graph

(1 ,2 ) ; (2 ,3) ; (3 ,4) ; (4 ,5) ; (5 ,6) ; (6 ,10) ; (6 ,7) ; (7 ,8) ; (8 ,9) ; (9 ,7) ; (9 ,10) ; (10 ,7) ; (9 ,6) ; (1 ,3) ; (10 ,1) ; (3 ,11) ; (10 ,11) ; (11 ,1) ; (3 ,10)

generated the Eulerian trail

3, 2, 1, 3, 4, 5, 6, 7, 8, 9, 7, 10, 6, 9, 10, 1, 11, 3, 10, 11

with only 3 recalculations of the distances.

Eunice’s bridge algorithm is a performant optimization of Fleury’s algorithm to find a Eulerian trail.

Of course, I welcome comments, criticism and suggestions.