Depth-first search in Python

Question

I wrote this DFS in Python and I was wondering if it correct. Somehow it seems too simple to me.

Each node is a class with attributes:

• visited: Boolean

• sons: list of nodes linked to the current node.

This code should work both for directed and undirected graphs.

def DFS(node):

    node.visited = True

    if node == None:
        return

    // perform some operation on the node
    do_something(node)

    to_visit = [son in node.sons if not son.visited]
    for son in to_visit:
        DFS(node)

Answer 1

DFS should keep track of all the nodes visited. Not the node.

The node only properties is it self, and it's children.

Check this amazing implementation:

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

dfs(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'}

As you can see DFS is called just once and it keeps track of visted nodes all the way, it will use pop(-1) so it will Depth-search, you could either change to pop(0), so it would Breadth-First Search. It's the same concept, the only difference is which node is visited in which order.

Your implementation will have some problems if the graph is too deep, because it could raise a Maximum recursion depth exceeded.

Answer 2

Having visited as a property of a node feels a bit like a leaky abstraction because it embeds the needs of a particular tree operation into the more general abstraction of graphs and nodes.

To me, a node is a data structure that has some pointers to zero or more children and perhaps stores a value - depending on the semantics of a particular graph. Consider an acyclic graph with all values at stored at leaves versus various cyclic graphs with values stored at each node.

In the cyclic graph case depth first search is not directly applicable until an appropriate starting node has been selected and though the concept of visited may make sense for some cyclic graph algorithms, it wouldn't in the case of other algorithms such as Dijkstra’s shortest path.

To separate concerns, a depth first search algorithm might create it's own object consisting of a generalized node object and a visited field...or use any of many other data structure approaches.

Without isolation algorithms operating on the graph must walk it a second time to clear the visited field. If there is concurrency, then graph algorithms must lock the entire data structure and the depth first search should have transaction semantics.

Answer 3

Checking if node == None makes no sense, immediately after having set node.visited = True. It will either crash or never match.

In any case, if mode is None is the standard way to check for None, and storing the visited flag in the graph modes themselves ruins the graph for future traversals.

Answer 4

Nope, it is not correct. The problem is that the to_visit list can change after visiting a child of the currect node(for example, on a full graph with 3 vertices your implementation will visit the third node twice(if you run the depth-first search from the first vertex)). However, it is easy to fix it. You can just iterate over all children of the current node and run a depth-first from a child if it has not been visited yet(using an if statement inside the for loop).