Kosaraju
Finds the strongly connected components of a directed graph with two depth-first searches, the second on the graph with every edge reversed.
Time complexity O(V+E), gograph function connectivity.Kosaraju.
How it works
Kosaraju's algorithm finds the strongly connected components with two depth-first searches. The first runs over the whole graph and notes each vertex as it finishes, after everything it leads to. The second runs on a copy of the graph with every edge reversed, and takes its start vertices from the last one to finish to the first.
The vertex that finishes last is in a component that no other component can reach. With the edges reversed, a search from it can't leave that component, so it collects exactly that component. Each later search does the same with what is left, so a component comes out before any component it can reach.
Both searches cost O(V+E), and the reversed copy takes O(V+E) more memory than Tarjan or Gabow need. In exchange, each search is a plain depth-first search with nothing more to track.
Web crawl
A hundred pages on ten sites that a crawler reached by following links, P1 to P100, where P stands for page. Pages are numbered site by site: an encyclopedia (P1 to P16), news (P17 to P30), a city (P31 to P37), a university (P38 to P46), a link directory (P47 to P52), docs (P53 to P62), a forum (P63 to P74), videos (P75 to P82), a blog (P83 to P90) and a shop (P91 to P100). Each edge counts the links from one page to another. The docs, shop and city sites never link back, and no page links to the directory.
A directed, weighted graph with 100 vertices and 274 edges.
Which groups of pages can all reach each other by following links, so a crawler that enters a group can get back to where it started?
The graph has 6 strongly connected components. The ones with more than one vertex are P47, P48, P49, P50, P51 and P52; P1, P2, P3, P4, P5, P6, P7, P8, P9, P10 and 56 more; P53, P54, P55, P56, P57, P58, P59, P60, P61 and P62; P31, P32, P33, P34, P35, P36 and P37; P91, P92, P93, P94, P95, P96, P97, P98, P99 and P100. The other component has one vertex, P90.
Step by step
- Kosaraju makes two passes. The first searches depth-first from each vertex no earlier search has reached, in the graph's vertex order, and pushes each vertex on a stack when it finishes, once every vertex it has an edge to has been reached. The second pass reverses every edge and searches again, taking its starts from the top of that stack. Each search in the second pass reaches exactly one strongly connected component.
- Start the first pass at P1, the first vertex.
- Follow P1 to P3.
- Follow P3 to P4.
- Follow P4 to P5.
- P5 has no unreached neighbors left, so it finishes, number 1. Push it on the finish stack. Back to P4.
396 more steps lead to the last one:
- Take the next 22 vertices off the top of the finish stack, P94 first and P5 last. They are already in components. Done. Kosaraju found 6 strongly connected components, 1 of them with one vertex. Each component is listed before every component it has an edge into. Every vertex now shows the component it belongs to.
Use it in Go
for _, component := range connectivity.Kosaraju(g) {
var names []string
for _, v := range component {
names = append(names, v.Label())
}
fmt.Println(strings.Join(names, ", "))
}
Example graphs
- Microservice calls, 9 vertices and 15 edges
- Import cycles, 18 vertices and 30 edges
- Linked web pages, 40 vertices and 114 edges
- Web crawl, 100 vertices and 274 edges
More in Connectivity
- 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.
- 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.