Tarjan

Finds the strongly connected components of a directed graph, the groups of vertices that can all reach each other, with one depth-first search.

Time complexity O(V+E), gograph function connectivity.Tarjan.

How it works

A strongly connected component is a group of vertices in a directed graph where each one can reach every other. Tarjan's algorithm finds them all in one depth-first search. It numbers the vertices in the order it reaches them and keeps them on a stack. Each vertex also tracks its lowlink, the smallest number it can reach through the vertices below it in the search and one more edge to a vertex still on the stack.

When the search finishes a vertex whose lowlink is still its own number, nothing it leads to can reach back to an earlier vertex on the stack. That vertex and every vertex above it on the stack form one component, and they leave the stack together. So a component comes out before any component that can reach it.

gograph keeps the search path in a slice instead of recursing, so a long chain doesn't grow the goroutine stack. It costs O(V+E). Use it to find services that call each other in a loop, modules that require each other, or the states of a machine that can all reach each other.

Linked web pages

Forty pages of a product website, P1 to P40, where P stands for page: the main site (P1 to P13), the blog (P14 to P19), landing pages (P20 to P24), the help center (P25 to P28), the docs (P29 to P38) and the status pages (P39 and P40). Each edge counts the links from one page to another. Only ads and emails lead to the landing pages, and the help center, docs and status pages never link back to the main site.

A directed, weighted graph with 40 vertices and 114 edges.

Which groups of pages can a visitor move around freely, getting from any page of a group to any other by following links?

The graph has 10 strongly connected components. The ones with more than one vertex are P29, P30, P31, P32, P33, P34, P35, P36, P37 and P38; P25, P26, P27 and P28; P39 and P40; P1, P2, P3, P4, P5, P6, P7, P8, P9, P10 and 8 more. The other 6 components have one vertex each: P19, P20, P21, P22, P23 and P24.

Step by step

  1. Tarjan searches depth-first from each vertex no earlier search has reached, in the graph's vertex order. It gives each vertex an index, the order the search reached it in, and a lowlink, the lowest index the vertex is known to reach among the vertices still on the stack. Every vertex goes on the stack when the search reaches it. When a vertex finishes with a lowlink equal to its own index, it is the root of a component: it and the vertices above it on the stack form one strongly connected component.
  2. Start at P1, the first vertex. P1 gets index 0 and lowlink 0 and goes on the stack.
  3. Follow P1 to P2. P2 gets index 1 and lowlink 1 and goes on the stack.
  4. P2 has an edge to P1, which is still on the stack with index 0. The lowlink of P2 drops from 1 to 0.
  5. Follow P2 to P3. P3 gets index 2 and lowlink 2 and goes on the stack.
  6. P3 has an edge to P1, which is still on the stack with index 0. The lowlink of P3 drops from 2 to 0.

135 more steps lead to the last one:

  1. Done. Tarjan found 10 strongly connected components, 6 of them with one vertex. Each component is listed after every component it has an edge into. Every vertex now shows the component it belongs to.

Use it in Go

for _, component := range connectivity.Tarjan(g) {
	var names []string
	for _, v := range component {
		names = append(names, v.Label())
	}
	fmt.Println(strings.Join(names, ", "))
}

Example graphs

More in Connectivity

  • Kosaraju: Finds the strongly connected components of a directed graph with two depth-first searches, the second on the graph with every edge reversed.
  • Gabow: Finds the strongly connected components of a directed graph with one depth-first search and two stacks, without the lowlink values of Tarjan's algorithm.
  • Condensation: Replaces each strongly connected component with one vertex. What is left is a DAG, so it can be sorted and scheduled.
  • Connected components: Splits a graph into its connected pieces, the groups of vertices joined to each other by some path, with one search per piece.
  • Cycle detection: Says whether a graph has a cycle, a way to follow its edges from a vertex back to the same vertex, and stops at the first one it finds.
  • Find a cycle: Returns the vertices of one cycle in order: the first one a depth-first search closes with an edge back to its search path.
  • Bridges and articulation points: Finds the edges and the vertices whose loss splits an undirected graph into more pieces, its single points of failure, from one depth-first search.

All algorithms