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

user_13142245 0
Viewed 93

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

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?

traversal depth-first-search graph python
2 Answers

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:

['a', 'c', 'f', 'b']
user_177698150

You check whether a node was visited or not when putting it on the stack, but only mark it visited when it is popped from the stack. This means any nodes that are on the stack are allowed to be pushed to the stack again (since they are not yet marked as visited at that point).

You need to either change visited to seen or something like that, to note that they have been added to the stack, and add the next_nodes to it instead of adding the node at visit time, or change the way next_nodes is generated in order to only take nodes that are neither in visited nor stack.

Unrelatedly, I'd make visited a set, not a list, for performance reasons.

user_2404430
Related