DEV Community

Bernice Waweru
Bernice Waweru

Posted on

Number of Connected Components in an Undirected Graph


Count the number of connected components in an undirected graph.


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.


def countComponents(graph):
    count = 0
    visited = set()
    for node in graph:
        if traverse(graph,node,visited) == True:
    return count
def traverse(graph,current,visited):
    if current in visited:
        return False
    for neighbor in graph[current]:
        traverse(graph, neighbor,visited)
    return True     
graph = {
    'a': ['c', 'b'],
    'b': ['d'],
    'c': ['e'],
    'd': ['f'],
    'e': [],
    'f': [],
Enter fullscreen mode Exit fullscreen mode

Top comments (0)