Kosaraju’s Algorithm
Finding Strongly Connected Components of a Graph
Until last week, I was under the impression that a graph represented data like this:
But it turns out that the more accurate depiction of a graph is really:
Graphs like the latter are able to form strongly connected components, as depicted by the triangle of three nodes on the left. These components contain vertices that can be reached from any of the other vertices. Koasaraju’s Algorithm is used to find these components using a Depth First Search.
What is a Graph?
Before we jump into the logistics of the algorithm, we need to establish some basics. According to Wikipedia, “a graph is a structure amounting to a set of objects in which some pairs of objects are in some sense ‘related’.” These objects translate to “mathematical abstractions called vertices and each pair of the related vertices is called an edge.” These edges can be either directed or undirected. Undirected edges do not show a head or tail, so the relationship is said to be a “two-way street.” Directed edges, however, do have a head that inserts from a vertex and a tail that points to another vertex to represent the “one-way” nature of the relationship.¹
What is a Depth First Search?
If you have ever come across a maze-solving algorithm like the one above, then you’ve seen a DFS in action. A DFS is “an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root [vertex] (selecting some arbitrary [vertex] as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.”² The gist is to start at some point (any point on a graph) and mark it as being visited before moving on to an adjacent vertex, then mark the adjacent vertex as having been visited and move on to an adjacent vertex and so on until reaching a dead end. At the dead end, the process is reversed and repeated to check for any other paths and once complete, prints a path of vertices.
Kosaraju’s Algorithm
As Science Blog puts it, “Kosaraju’s algorithm is amazingly simple. It uses a very clever trick based on the fact that if you reverse all of the edges in a graph, the resulting graph has the same strongly connected components as the original.”³ The algorithm is broken down into 3 steps:
- DFS to create a stack: search all vertices and sort according to finishing time. This means that during the DFS, the vertices that finish first are put on the bottom of the stack and the last vertex reached in the DFS is put on the top of the stack.
2. Transpose Graph: reverse all the edges of the original graph
3. DFS on stack: using the stack created in Step 1, perform DFS on reversed edges
There are 4 SCC on this graph as each vertex is it’s own SCC, so 6–4–5, 1, 2 and 3 are all the SCCs.
Conclusion
Kosaraju’s Algorithm is very useful in performing DFS on directed graphs to find any SCCs. The time complexity is linear, so it is not an expensive algorithm and can greatly optimize our code when exploring graphs.