Skip to content

Commit fbdd91b

Browse files
Fix typo in "Finding Bridges"
Closes #1508
1 parent 6f7cf7a commit fbdd91b

File tree

1 file changed

+1
-1
lines changed

1 file changed

+1
-1
lines changed

src/graph/bridge-searching.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ Pick an arbitrary vertex of the graph $root$ and run [depth first search](depth-
2222

2323
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.
2424

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:
25+
So, let $\mathtt{tin}[v]$ denote entry time for node $v$. We introduce an array $\mathtt{low}$ which will let us store the earliest entry time of the node 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:
2626

2727
$$\mathtt{low}[v] = \min \left\{
2828
\begin{array}{l}

0 commit comments

Comments
 (0)