Bernice Waweru
Posted on February 21, 2022
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))
💖 💪 🙅 🚩
Bernice Waweru
Posted on February 21, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
