Number of Components in an Undirected Graph

Patrick Leaton

Published: July 5, 2021, 9:37 p.m.

Problem Description

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

Output: 2

Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

Output:  1

Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

The description was taken from https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/.

Problem Solution

#DFS

#O(N+E) Time, O(N+E) Space

class Solution:

def countComponents(self, n: int, edges: List[List[int]]) -> int:

count = 0

adjacency, seen = {}, {}

for node in range(0, n):

adjacency[node] = []

seen[node] = False

for node, neighbor in edges:

adjacency[node].append(neighbor)

adjacency[neighbor].append(node)

def dfs(node:int) -> None:

if seen[node]:

return

seen[node] = True

for neighbor in adjacency[node]:

if not seen[neighbor]:

dfs(neighbor)

for node in range(0,n):

if not seen[node]:

count += 1

dfs(node)

return count

#BFS

#O(N+E) Time, O(N+E) Space

class Solution:

def countComponents(self, n: int, edges: List[List[int]]) -> int:

count = 0

adjacency, seen = {}, {}

for node in range(0, n):

adjacency[node] = []

seen[node] = False

for node, neighbor in edges:

adjacency[node].append(neighbor)

adjacency[neighbor].append(node)

def bfs(node:int) -> None:

queue = collections.deque([node])

while queue:

node = queue.popleft()

seen[node] = True

for neighbor in adjacency[node]:

if not seen[neighbor]:

seen[neighbor] = True

queue.append(neighbor)

for node in range(0,n):

if not seen[node]:

count += 1

bfs(node)

return count

Problem Explanation

This problem is nearly the same as Number of Provinces.

We can count the number of connected components by running a Depth-First Search, or a Breadth-First Search.

Any connected nodes will be visited when the search is run on its neighbor. Any time we need to visit a new node, we know that we are visiting a new component, so we can increment a counter each time this happens to get our answer.

Recursive Depth-First Search

We will start by initializing our count of components, our adjacency list that maps each neighbor to each node so that we can create a graph without physically instantiating nodes using the edges input, and our seen dictionary that keeps track of whether we have visited each specific node.

count = 0

adjacency, seen = {}, {}

Once we have initialized the adjacency list and seen, we will go through each node, place it in the adjacency list with an initially empty list of neighbors, and mark it as false within seen, since we have not seen it yet within a search.

for node in range(0, n):

adjacency[node] = []

seen[node] = False

Since this is an undirected graph, the edge between each node and each neighbor goes to and from each other.

To signify this, we will go through edges input to map each node to its neighbor and each neighbor to the node, so that it is a two-way edge, undirected edge.

for node, neighbor in edges:

adjacency[node].append(neighbor)

adjacency[neighbor].append(node)

Next, we will build our recursive, dfs function.

The function will do a generic DFS, it will take the node that was passed to it check if it has been seen before, mark it as seen if not, then recurse any unseen neighbors of the node to do the same thing.

def dfs(node:int) -> None:

if seen[node]:

return

seen[node] = True

for neighbor in adjacency[node]:

if not seen[neighbor]:

dfs(neighbor)

Now, we just need to make our initial DFS calls.

For each node we have, if the node hasn't been seen before then it is part of a new component that hasn't been seen before.

When that happens, we will increment the count and perform a DFS on the current, unseen node.

Just to reiterate, a DFS/BFS will stop once it has exhausted its list of connected nodes adjacent to each other. That means we only need to make one initial call on a single node of a component because our DFS/BFS will travel to the rest until there are no more neighbors to travel to.

for node in range(0,n):

if not seen[node]:

count += 1

dfs(node)

Once we have traversed each node, we will return the count of the components we found.

return count

Iterative Breadth-First Search

The only difference between the BFS and DFS version, basically the only difference in general, is a BFS uses a queue and a DFS uses a stack. The BFS will traverse each component level by level instead of the previously used DFS that will traverse it depth by depth.

All we need to do here is swap the recursive, dfs function for an iterative, bfs function.

The function will take a node and push it into a queue.

def bfs(node:int) -> None:

queue = collections.deque([node])

While the queue still has nodes that we need to visit, we will continue to pop a node, visit it, visit its unseen neighbors, then push its neighbors on the queue to repeat the process.

while queue:

node = queue.popleft()

seen[node] = True

for neighbor in adjacency[node]:

if not seen[neighbor]:

seen[neighbor] = True

queue.append(neighbor)