Home Is it possible to traverse all connected nodes in a graph with DFS when cycles are present?

Questions

Is it possible to traverse all connected nodes in a graph with DFS when cycles are present?

May 19, 2022

g = {'a':['b','c'],
     'b':['a','f'],
     'c':['a','f'],
     'd':['c','e'],
     'e':['d'],
     'f':['c','b'],
     }

def dfs(graph, node):
  stack = [node]
  visited = []
  while stack:
    current = stack.pop()
    visited.append(current)
    next_nodes = list(filter(lambda x: x not in visited, graph[current]))
    stack.extend(next_nodes)
  return visited

dfs(g,'a')   
>>>
['a', 'c', 'f', 'b', 'b']

My solution is unable to reach d or e. Also it visits b twice, which is bizarre. How could this code be altered to traverse all nodes (if possible) without repeats to the visited array?

>Solution :

You need to check whether a given node is already on the stack, else you may end up processing the same node twice:

def dfs(graph, node):
    stack = [node]
    visited = []
    while stack:
        current = stack.pop()
        visited.append(current)
        next_nodes = list(filter(lambda x: x not in visited + stack, graph[current]))
        stack.extend(next_nodes)
    return visited

As for the issue of some nodes not being visited, none of the nodes reachable from 'a' have any outgoing neighbors to 'd' or 'e'. If your graph is meant to be undirected, you need to make sure that you’re adding all the right entries for each node. If your graph is meant to be directed, this is expected behavior.

We can also optimize this code. You could maintain a separate seen set, to be able to check more quickly whether you’ve seen a node or not (seen == "on the stack or already visited"):

def dfs(graph, node):
    stack = [node]
    seen = {node}
    visited = []
    while stack:
        current = stack.pop()
        visited.append(current)
        next_nodes = list(filter(lambda x: x not in seen, graph[current]))
        stack.extend(next_nodes)
        seen.update(next_nodes)

    return visited

This outputs: