I am learning graph theory and am having a hard time counting the number of connected components in a graph. Can someone help me out? I am trying to come up with an iterative version because I am a bit shaky on recursion (still getting the hang of it) so I want to master the iterative version first. Below is what I have so far. I am going through every node in the graph and running dfs on it but I seem to be returning a count of 5 instead of 2 for the example graph and I am not sure why.
graph = {
0: [8, 1, 5],
1: [0],
5: [0, 8],
8: [0, 5],
2: [3, 4],
3: [2, 4],
4: [3, 2]
}) # return -> count of 2
def connected_components_count(graph):
visited = set()
stack = []
count = 0
for node in graph:
if node not in visited:
stack.append(node)
visited.add(node)
while len(stack) != 0:
current = stack.pop()
for neighbor in graph[current]:
if neighbor not in visited:
stack.append(neighbor)
visited.add(neighbor)
else:
count += 1
return count
Got one test case to pass by only increasing the count after a dfs has been run on a node
def connected_components_count(graph):
visited = set()
stack = []
count = 0
for node in graph:
if node not in visited:
stack.append(node)
visited.add(node)
while len(stack) != 0:
current = stack.pop()
for neighbor in graph[current]:
if neighbor not in visited:
stack.append(neighbor)
visited.add(neighbor)
count += 1
return count
but now failing this case
graph = {
2: [3, 1],
3: [2, 1],
1: [2, 3]
} # -> return count 2
This ^ is a leetcode test case and wants to return 2 but there is only one component in this graph right? all of the vertices are connected?
Okay finally got it there is a hidden node in that specific test case that counts as one component. thanks for all the help everyone and for pointing me in the right direction!
>Solution :
else:
count += 1
Incorrect.
Increment the count IFF the node has NOT been visited
