You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
<!--?title Searching for bridges in a graph in O(N+M) -->
1
+
<!--?title Finding bridges in a graph in O(N+M) -->
2
2
3
-
# Searching for bridges
3
+
# Finding bridges in a graph in $O(N+M)$
4
4
5
-
Suppose that we are given an undirected graph. A bridge is defined as an edge, whose removal makes the graph disconnected(or more precisely, increases the number of connected components). You want to find all the bridges in a given graph.
5
+
We are given an undirected graph. A bridge is defined as an edge which, when removed, makes the graph disconnected(or more precisely, increases the number of connected components in the graph). The task is to find all bridges in the given graph.
6
6
7
-
Informally, the problem is formulated as follows: Given a map of cities with roads between them, find all "important" roads, i.e. roads whose removal leads to disappearance of the path between some pair of cities.
7
+
Informally, the problem is formulated as follows: given a map of cities connected with roads, find all "important" roads, i.e. roads which, when removed, cause disappearance of a path between some pair of cities.
8
8
9
-
Below, we describe the algorithm based of[depth first search](http://e-maxx.ru/algo/dfs), having running time $O(n+m)$, where $n$ is the number of vertices, and $m$ is the number of edges in the graph.
9
+
The algorithm described here is based on[depth first search](./graph/depth-first-search.html) and has $O(N+M)$ complexity, where $N$ is the number of vertices and $M$ is the number of edges in the graph.
10
10
11
-
Note that the website also describes an [online algorithm for finding bridges](http://e-maxx.ru/algo/bridge_searching_online) - in contrast to the offline algorithm described here, the online algorithm is able to maintain all bridges in a graph that is changing(new edges are being added).
11
+
Note that there also exists an [online algorithm for finding bridges (ru)](http://e-maxx.ru/algo/bridge_searching_online) - unlike the offline algorithm described here, the online algorithm is able to maintain the list of all bridges in a changing graph (assuming that the only type of change is addition of new edges).
12
12
13
13
## Algorithm
14
14
15
-
Run [DFS](http://e-maxx.ru/algo/dfs) from an arbitrary vertex of the graph; lets denote it through $root$. We note the following fact(which is easy to prove):
15
+
Pick an arbitrary vertex of the graph $root$ and run [depth first search](./graph/depth-first-search.html) from it. Note the following fact(which is easy to prove):
16
16
17
-
- Let's say we are in the DFS, and looking through the edges from vertex $v$. Then for some edge $(v, to)$, it is a bridge if the vertices $to$ and it's descendants in the DFS tree have no back-edges to vertex $v$ or any of it's ancestors. Otherwise, the edge must not be a bridge. (In fact, we check the condition that there is no other way from $v$ to $to$ except for edge $(v, to)$ traversing the DFS tree.)
17
+
- Let's say we are in the DFS, looking through the edges starting from vertex $v$. The current edge $(v, to)$is a bridge if and only if none of the vertices $to$ and its descendants in the DFS traversal tree has a back-edge to vertex $v$ or any of its ancestors. (Indeed, this condition means that there is no other way from $v$ to $to$ except for edge $(v, to)$)
18
18
19
-
Now we have to learn how to effectively verify this fact for each vertex. For doing this, we use "time of entry into node", computed by the depth first search algorithm.
19
+
Now we have to learn to check this fact for each vertex efficiently. We'll use "time of entry into node" computed by the depth first search.
20
20
21
-
So, let $tin[v]$ denote the the depth first search time of node $v$. Now, we introduce the array $fup[v]$, which is the minimum of $tin[v]$, the DFS time of all nodes $p$ that are connected to node $v$ via back-edge $(v, p)$ and all the values of $fup[to]$ for each vertex to which is a direct child of $v$ in the DFS tree.
21
+
So, let $tin[v]$ denote entry time for node $v$. We introduce an array $fup$ which will let us check the fact for each vertex $v$. $fup[v]$is the minimum of $tin[v]$, the entry time for all nodes $p$ that are connected to node $v$ via a back-edge $(v, p)$ and the values of $fup[to]$ for each vertex $to$ which is a direct descendant of $v$ in the DFS tree:
22
22
23
-
23
+
24
24
25
-
Now, there is a back edge from node $v$ or it's descendants if there is a son $to$ of node $v$ such that $fup[to] \leq tin[v]$.(If $fup[to] = tin[v]$, it means back edge comes directly to $v$, otherwise it comes to some ancestor).
25
+
Now, there is a back edge from vertex $v$ or one of its descendants to one of its ancestors if and only if vertex $v$ has a child $to$ for which $fup[to] \leq tin[v]$.If $fup[to] = tin[v]$, the back edge comes directly to $v$, otherwise it comes to one of the ancestors of $v$.
26
26
27
-
Thus, if the current edge $(v, to)$ in the DFS tree satisfies $fup[to] > tin[v]$, then it must be a bridge; otherwise it isn't one.
27
+
Thus, the current edge $(v, to)$ in the DFS tree is a bridge if and only if $fup[to] > tin[v]$.
28
28
29
-
##Implementation
29
+
##Implementation
30
30
31
-
Regarding the implementation, here we need to distinguish 3 cases: when we are on an edge to a child in DFS tree, when we try to go on a back edge to some ancestor and when we are going in the reverse direction to our parent. Therefore, these are the cases accordingly:
31
+
The implementation needs to distinguish three cases: when we go down the edge in DFS tree, when we find a back edge to an ancestor of the vertex and when we return to a parent of the vertex. These are the cases:
32
32
33
-
- $used[to] = false$ - DFS tree edges criteria;
34
-
- $used[to] = true$ && $to \neq parent$ - back edge to some ancestor criteria;
35
-
- $to = parent$ - Criteria for edge to be edge to parent in DFS tree.
33
+
- $used[to] = false$ - the edge is part of DFS tree;
34
+
- $used[to] = true$ && $to \neq parent$ - the edge is back edge to one of the ancestors;
35
+
- $to = parent$ - the edge leads back to parent in DFS tree.
36
36
37
-
Thus, to implement, we need a depth first search function with all the information for a current node.
37
+
To implement this, we need a depth first search function which accepts the parent vertex of the current node.
38
38
39
39
C++ implementation <spanclass="toggle-code">Show/Hide</span>
40
40
@@ -45,42 +45,43 @@ bool used[MAXN];
45
45
int timer, tin[MAXN], fup[MAXN];
46
46
47
47
voiddfs (int v, int p = -1) {
48
-
used[v] = true;
49
-
tin[v] = fup[v] = timer++;
50
-
for (size_t i = 0; i < g[v].size(); ++i) {
51
-
int to = g[v][i];
52
-
if (to == p) continue;
53
-
if (used[to])
54
-
fup[v] = min (fup[v], tin[to]);
55
-
else {
56
-
dfs (to, v);
57
-
fup[v] = min (fup[v], fup[to]);
58
-
if (fup[to] > tin[v])
59
-
IS_BRIDGE(v,to);
60
-
}
61
-
}
48
+
used[v] = true;
49
+
tin[v] = fup[v] = timer++;
50
+
for (size_t i = 0; i < g[v].size(); ++i) {
51
+
int to = g[v][i];
52
+
if (to == p) continue;
53
+
if (used[to])
54
+
fup[v] = min (fup[v], tin[to]);
55
+
else {
56
+
dfs (to, v);
57
+
fup[v] = min (fup[v], fup[to]);
58
+
if (fup[to] > tin[v])
59
+
IS_BRIDGE(v,to);
60
+
}
61
+
}
62
62
}
63
63
64
64
void find_bridges() {
65
-
timer = 0;
66
-
for (int i = 0; i < n; ++i)
67
-
used[i] = false;
68
-
for (int i = 0; i < n; ++i)
69
-
if (!used[i])
70
-
dfs (i);
65
+
timer = 0;
66
+
for (int i = 0; i < n; ++i)
67
+
used[i] = false;
68
+
for (int i = 0; i < n; ++i)
69
+
if (!used[i])
70
+
dfs (i);
71
71
}
72
72
```
73
73
74
-
Here, the main function calls function $find$_$bridges$ which produces necessary initialization and starts depth first search in all components of a graph.
74
+
Main function is `find_bridges`; it performs necessary initialization and starts depth first search in each connected component of the graph.
75
75
76
-
Function $IS$_$BRIDGE(a, b)$ - is a function that will produce output to the fact that edge $(a, b)$ is a bridge.
76
+
Function `IS_BRIDGE(a, b)` is some function that will process the fact that edge $(a, b)$ is a bridge, for example, print it.
77
77
78
-
Constant $MAXN$ at beginning of code is initialised to maximum number of nodes in the graph.
78
+
Constant `MAXN` at beginning of code should be initialized to the maximum possible number of vertices in the input graph.
79
79
80
-
It should be noted that this does not work correctly if multiple edges are present in the graph, as it actually ignores their presence. Of course, multiple edges must not be a part of the answer, so checks must be made in the function $IS$_$BRIDGE$. Another way to work with multiple edges more accurately is to transfer the number of edges by which we entered the current node(we all need to store this additionally).
80
+
Note that this implementation malfunctions if the graph has multiple edges, since it ignores them. Of course, multiple edges will never be a part of the answer, so `IS_BRIDGE` can check additionally that the reported bridge does is not a multiple edge. Alternatively it's possible to pass to `dfs` the index of the edge used to enter the vertex instead of the parent vertex (and store the indices of all vertices).
0 commit comments