DEV Community 👩‍💻👨‍💻 is a community of 963,274 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))
``````