non_recursive_DFS.py

def dfs_pre_order(root,edges):
    stack = [root]
    visited = set()
    while stack:
        v = stack.pop()
        if v not in visited:
            print "PRE-ORDER visting: " + v
            visited.add(v)
            for u in edges[v]:
                stack.append(u)

                
def dfs_pre_order_branching(root,edges):
    """ adds all neighbour vertices to the set of visited vertices before continuing.
    this is *not* depth first search
    will still traverse the whole graph in a 'greedy' manner
    but cycles are treated slightly differently
    if A <-> B, A <-> C and B <-> C then instead of
    finding the cycle A -> B -> C -> (A)
    it will find A -> B -> (C) as it treats all of A's neighbours
    as visited.
    this means that the stack never contains duplicate vertices
    """
    stack = [root]
    visited = set([root])
    while stack:
        v = stack.pop()
        print "PRE-ORDER visting: " + v
        for u in edges[v]:
            if u not in visited:
                stack.append(u)
                visited.add(u)

                
                
def dfs_post_order(root,edges):
    stack   = [root]
    path    = [None] # use None so we dont have to test if path is empty (root) 
    visited = set()
    while stack:
        if stack[-1] == path[-1]: # without [None] we would have 'if path and stack[-1] == ...'
            v = stack.pop()
            path.pop() # returns v
            print "POST-ORDER visting: " + v
            visited.add(v)
        else:
            v = stack[-1]
            if v in visited:
                stack.pop()
            else:
                visited.add(v)
                path.append(v)
                for u in edges[v]:
                    stack.append(u)                

                    
def dfs_pre_post_order(root,edges):
    stack   = [root]
    path    = [None]
    visited = set()
    while stack:
        if stack[-1] == path[-1]:
            v = stack.pop()
            path.pop() # returns v
            print "  POST-ORDER visting: " + v
            visited.add(v)
        else:
            v = stack[-1]
            if v in visited:
                stack.pop()
            else:
                print "PRE-ORDER visiting: " + v
                visited.add(v)
                path.append(v)
                for u in edges[v]:
                    stack.append(u)
                    
                
edges = {'a':{'b','d'},
         'b':{'a','c'},
         'c':{'b','d','g'},
         'd':{'a','c','e','f'},
         'e':{'d','f'},
         'f':{'d','e'},
         'g':{'c'}
}