Fleury’s algorithm is an algorithm for finding an Eulerian path/cycle in an undirected graph. It relies on being able to detect bridges in such a graph. A bridge is an edge, which when deleted, increases the number of connected components. Note that this is distinct from the concept of strongly connected components, which is relevant only for directed graphs. There is also an algorithm for detecting strong bridges, the removal of which increases the number of strongly connected components.
This is an implementation of such a bridgedetection algorithm, which uses a single pass of DFS and runs in linear time with respect to the number of edges. I am not sure if it’s similar to Tarjan’s algorithm, since I couldn’t fully understand the description of the algorithm as given on Wikipedia, but the core idea is probably similar.
Imaging doing a preorder traversal of a given graph, and numbering off each
node when you visit it for the first time. pre
is a dictionary which stores
that numbering. In this context, let’s say a node A is considered earlier
than another node B if A’s number is smaller than B’s number.
low
, on the other hand, is a dictionary which stores the earliest node that is
reachable from a given node, including itself. Note that when considering this,
we must be careful to
ignore “back” edges. “Back” in this sense of the word refers to a direction that is
opposite of the preorder traversal.
The idea then, of using pre
and low
, is this:
From a given, earlier, node A, looking at some adjacent, later, neighbour B, if
low[B]
is equal topre[B]
, then the edge AB is a bridge.
The reason for this is because a bridge is any edge that is not part of a cycle. If, from B, we can reach an earlier node than A, then it means the edge AB is part of a larger cycle, and therefore not a bridge.
There are only 2 situations we have to consider when looking at the possible
values of pre[B]
:
 It is equal to
low[B]
. This means that B is either a terminal node, or there exists some cycle that B is a part of, but A is not.  It is lower than
low[B]
. This means that, aside from actually going backwards through A, its preorder predecessor, there exists some cycle that connects B eventually back to A. Therefore, the edge AB is not a cycle.
Let’s take an undirected graph like this for example:
E

A  B  C  D
 

Then pre
will be:
pre = {
'A': 0,
'B': 1,
'C': 2,
'D': 3,
'E': 4,
}
and low
will be:
low = {
'A': 0,
'B': 1,
'C': 1,
'D': 1,
'E': 4,
}
Note that low[B]
is 1, not 0, even though the graph is supposedly undirected,
since B > A runs opposite to the preorder traversal.
Here is a complete implementation in Python:
class Graph:
def __init__(self, connections: List[Tuple[str, str, int]], directed: bool = False):
self._graph: DefaultDict[str, Dict[str, int]] = defaultdict(lambda: defaultdict(int))
self._directed = directed
for c1, c2, weight in connections:
self.add_edge(c1, c2, weight)
def add_edge(self, start: str, end: str, weight: int):
self._graph[start][end] = weight
if not self._directed:
self._graph[end][start] = weight
def bridge_detection(self) > List[Tuple[str, str]]:
bridges = []
pre: Dict[str, int] = {}
low: Dict[str, int] = {}
count = [0] # mimic a mutable integer
for node in self._graph.keys():
if node not in pre:
self.bridge_dfs(bridges, low, pre, count, node, node)
return bridges
def bridge_dfs(self, bridges, low, pre, count, u, v):
# assign a preorder numbering to this node
pre[v] = count[0]
count[0] += 1
# tentatively assign low[v] to pre[v]
low[v] = pre[v]
for neighbour in self._graph[v]:
# for each neighbour, if they haven't been visited yet
# visit them
if neighbour not in pre:
self.bridge_dfs(bridges, low, pre, count, v, neighbour)
# if any neighbour has an earlier reachable node, we need to
# update the parent's one as well
low[v] = min(low[v], low[neighbour])
# for any neighbour, if its earliest reachable node is itself
# then there is no other way to reach the neighbour except from v
# therefore, the edge from v to this neighbour is a bridge
if low[neighbour] == pre[neighbour]:
bridges.append((v, neighbour))
# we must ignore "back" edges while iterating over the neighbours
elif neighbour != u:
low[v] = min(low[v], low[neighbour])
graph = Graph([
('A', 'B', 1),
('B', 'C', 1),
('C', 'E', 1),
('C', 'D', 1),
('D', 'B', 1),
])
print(graph.bridge_detection()) # [('A', 'B'), ('C', 'E')]
Using this, the overall running time of Fleury’s algorithm is O(E^2^), since every time we traverse and remove the justtraversed edge, we must rerun the bridge detection algorithm. There are faster ways to find Eulerian paths/cycles (see Hierholzer’s algorithm, which runs in overall linear time by exhaustively drawing disjunct cycles).