## DEV Community π©βπ»π¨βπ» is a community of 963,503 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Bernice Waweru

Posted on

# Number of Connected Components in an Undirected Graph

## 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
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))
``````