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!

CodePudding user response：

   else:
      count  = 1

Incorrect.

Increment the count IFF the node has NOT been visited