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
Copy file name to clipboardExpand all lines: src/graph/bridge-searching.md
+13-6Lines changed: 13 additions & 6 deletions
Original file line number
Diff line number
Diff line change
@@ -22,20 +22,26 @@ Pick an arbitrary vertex of the graph $root$ and run [depth first search](depth-
22
22
23
23
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.
24
24
25
-
So, let $tin[v]$ denote entry time for node $v$. We introduce an array $low$ which will let us check the fact for each vertex $v$. $low[v]$ is the minimum of $tin[v]$, the entry times $tin[p]$ for each node $p$ that is connected to node $v$ via a back-edge $(v, p)$ and the values of $low[to]$ for each vertex $to$ which is a direct descendant of $v$ in the DFS tree:
25
+
So, let $\mathtt{tin}[v]$ denote entry time for node $v$. We introduce an array $\mathtt{low}$ which will let us store the node with earliest entry time found in the DFS search that a node $v$ can reach with a single edge from itself or its descendants. $\mathtt{low}[v]$ is the minimum of $\mathtt{tin}[v]$, the entry times $\mathtt{tin}[p]$ for each node $p$ that is connected to node $v$ via a back-edge $(v, p)$ and the values of $\mathtt{low}[to]$ for each vertex $to$ which is a direct descendant of $v$ in the DFS tree:
26
26
27
-
$$low[v] = \min \begin{cases} tin[v] \\ tin[p]& \text{ for all }p\text{ for which }(v, p)\text{ is a back edge} \\ low[to]& \text{ for all }to\text{ for which }(v, to)\text{ is a tree edge} \end{cases}$$
27
+
$$\mathtt{low}[v] = \min \left\{
28
+
\begin{array}{l}
29
+
\mathtt{tin}[v] \\
30
+
\mathtt{tin}[p] &\text{ for all }p\text{ for which }(v, p)\text{ is a back edge} \\
31
+
\mathtt{low}[to] &\text{ for all }to\text{ for which }(v, to)\text{ is a tree edge}
32
+
\end{array}
33
+
\right\}$$
28
34
29
-
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 $low[to] \leq tin[v]$. If $low[to] = tin[v]$, the back edge comes directly to $v$, otherwise it comes to one of the ancestors of $v$.
35
+
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 $\mathtt{low}[to] \leq \mathtt{tin}[v]$. If $\mathtt{low}[to] = \mathtt{tin}[v]$, the back edge comes directly to $v$, otherwise it comes to one of the ancestors of $v$.
30
36
31
-
Thus, the current edge $(v, to)$ in the DFS tree is a bridge if and only if $low[to] > tin[v]$.
37
+
Thus, the current edge $(v, to)$ in the DFS tree is a bridge if and only if $\mathtt{low}[to] > \mathtt{tin}[v]$.
32
38
33
39
## Implementation
34
40
35
41
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:
36
42
37
-
- $visited[to] = false$ - the edge is part of DFS tree;
38
-
- $visited[to] = true$ && $to \neq parent$ - the edge is back edge to one of the ancestors;
43
+
- $\mathtt{visited}[to] = false$ - the edge is part of DFS tree;
44
+
- $\mathtt{visited}[to] = true$ && $to \neq parent$ - the edge is back edge to one of the ancestors;
39
45
- $to = parent$ - the edge leads back to parent in DFS tree.
40
46
41
47
To implement this, we need a depth first search function which accepts the parent vertex of the current node.
@@ -101,3 +107,4 @@ Note that this implementation malfunctions if the graph has multiple edges, sinc
0 commit comments