Number of Connected Components in an Undirected Graph

#dsa #python

Instructions

Count the number of connected components in an undirected graph.

Approach

We initialize count and iterate through every node in the graph traversing through its neighbors as far as possible. We increment count by 1 when there are no more nodes in the connected component.
We also need to keep track of the visited nodes to avoid a loop and duplicate look up.

Implementation

def countComponents(graph):
    count = 0
    visited = set()
    for node in graph:
        if traverse(graph,node,visited) == True:
            count+=1
    return count
def traverse(graph,current,visited):
    if current in visited:
        return False
    visited.add(current)
    for neighbor in graph[current]:
        traverse(graph, neighbor,visited)
    return True     
graph = {
    'a': ['c', 'b'],
    'b': ['d'],
    'c': ['e'],
    'd': ['f'],
    'e': [],
    'f': [],
    'g':[]
}
print(countComponents(graph))