Weakly connected components refer to connected components in an undirected graph, also known as friend circle problem. This post documents three common solutions to figure out the number of connected components in graphs.

Problem Description

Connection components refers to those vertices in a graph that can reach each other through a path, which is consist of edges. They are weakly connected components if the edges are regarded as undirected. The problem is to count the number of weakly connected components in a given undirected graph, represented in adjacency matrix.

DFS

The straight forward idea is Depth First Search (DFS) traverses through the graph, varying the root vertex from the first one to the last one, but only start DFS and count at an unvisited root vertex. The following code is an example implementation:

BFS (Label Propogation)

It not easy for DFS to execute in parallel, and the alternative is Breadth First Search (BFS). Vertices are initialized to hold their ids as labels, and propogate their labels if they are in the working list (frontier). Parallelism happens when there are multiple vertics in the working list. Start from the vertex having the smallest id, the behavior for a vertex receiving a label is compare the comming label with holding label and go with the smaller one. Here comes an example implementation:

Union Find

Different from DFS and BFS, union find is a edge-centric solution. Each vertex initializes label with their own id, which means we start with number of vertices sets. Then the edge list streams in, and we perform union operation to merge two sets, to which those two end vertices of the edge belong. The union operation needs to change the root of one of the two sets, labeling it with any vertex from the another set (see the article for demonstration). To facilitate find, which starts from a vertex tracing back until the root of the set, we usually label the end vertex, the root of that vertex to the root of another set, as shown in the following code snippet:

Credits

• leetcode - Thanks for offering a platform where I can see others’ solutions and test my code.
• Disjount Set Union (Union Find) - Thanks Prateek Garg, it is a good article with plenty of figures illustrating the union find well.