Depth-first search in Python 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)
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.