# Tarjan's Algorithm **An algorithm for finding [[Strongly Connected Component|strongly connected components]] using [[depth-first search]].** ![[Tarjan'sAlgorithm1.svg|500]] *** ![[Tarjan'sAlgorithm2.svg|500]] *Tarjan's algorithm on part of a graph; the DFS first assigns to each vertex two initially equal values, `dsc(v)` (left) and `low(v)` (right), the second of which is later updated for some vertices* ***Worst-case [[time complexity]]:*** $O(V + E)$ > [!Algorithm] > 1. Maintain an initially empty [[stack]] of unassigned vertices. > 2. For each unvisited vertex `v`, > 1. Assign to `dsc(v)` and `low(v)` the position of the vertex in depth-first search order. > 2. Push `v` onto the stack. > 3. For all neighbours `w` of `v`, > - If `dsc(w)` is unassigned, > 1. Recurse on `w` from step 2. > 2. Assign to `low(v)` the minimum of `low(v)` and `low(w)`. > - Else if `w` is in the stack, > 1. Assign to `low(v)` the minimum of `low(v)` and `dsc(w)`. > 4. If `dsc(v)` is equal to `low(v)`, pop the stack until `v` is popped from the stack. The popped vertices form a strongly connected component. > [!infobox] Tarjan's algorithm > | | | |:------------------------------------ | -------- | | ***Worst-case [[time complexity]]*** | $O(V+E)$ | > <br> > <br> **Tarjan's algorithm** is an algorithm that finds [[Strongly Connected Component|strongly connected components]] in a [[graph]] by traversing the graph with a *depth-first search* and assigning two values to each vertex `v` a value indicating the order in which they are encountered, `dsc(v)`, and a value indicating the vertex with the lowest `dsc` that can be reached from `v`, `low(v)`. The values of `low` are updated as the algorithm is executed. If, after the completion of a branch of depth-first search, the values of `dsc` and `low` are equal for some vertex, then that vertex forms the 'root' of a strongly connected component and the other constituent vertices are in the stack above it. ## Time complexity Tarjan's algorithm is an implementation of depth-first search without any significant modifications besides the usage of a stack and the minimum function. Thus, the worst-case time complexity is $O(V+E)$. ## Example > [!Example] > Tarjan's algorithm first runs a depth-first search and *enumerates* every vertex based on their encounter order, which provides the value of `dsc(v)`. Initially, the only reachable vertices of any vertex is itself and so `low(v)` is set equal to `dsc(v)`. > > In the above example, the vertices are encountered in the order $a\rightarrow b\rightarrow c$, and thus they are assigned the numbers $1, 2,$ and $3$ accordingly for both `dsc(v)` and `low(v)`. > > Once the depth-first search has *completed a branch*, the recursion call returns are followed by *updates to the values* of `low` for all vertices in the branch. As $a$ is the vertex with the lowest `dsc` reachable from $c$, the value of `low(c)` becomes $0$. The same is true for $b$, which can reach $a$ through $c$. > > The last recursion call return verifies that the values of `dsc(a)` and `low(a)` are equal, and thus it can be considered the *root* of a strongly connected component. As $b$ and $c$, which are in this component, were encountered after $a$, they are in the stack above $a$ and the stack can be *popped up to and including* $a$ to obtain all vertices of the strongly connected component rooted at $a$.