Go: Strongly Connected Components in Graphs

Find SCCs in directed graphs with Golang

Photo by Alina Grubnyak on Unsplash

Imagine you have to write code to discover groups inside a social network, so then you can suggest them to follow each other or to like some page based on their shared interest.

People in the network can be represented as the vertices of a graph, and the groups as the strongly connected components of it.

A strongly connected component (SCC) of a directed graph is the portion of the graph where exists a path between all pairs of vertices. This only works for directed graphs (i.e. where the edges have a direction, they indicate a one-way relationship from one vertex to another).

For example, Figure 1.1 shows a directed graph with four strongly connected components.

The asymptotically best algorithm to find SCCs is Kosaraju’s algorithm, which runs in O(V+E) time.

If you are given a directed graph (G) this algorithm has four steps:

1. Create an empty stack.
2. Do depth-first search (DFS) traversal on G, and push each vertex onto the stack.
3. Create the transpose (GT) of G.
4. Pop the elements from the stack in a LIFO order until it’s empty. When popping the element call DFS on it. Each call will output an SCC.

Writing the code

We will represent our graph as an adjacency list. This means that an array of lists is used, and the size of the array is equal to the number of vertices. In Go we can use a slice of int slices, or [][]int.

We will create four functions:

• scc will be responsible for running the whole procedure.
• dfs will do a depth-first search for the first time and append vertices to the stack
• transpose will transpose the graph
• visit will run a depth-first search for the second time and print out the strongly connected components

Let’s see the whole code first, and then we will go over it in detail: