(graph, root=None, filter=null())
return (spanning_tree, pre, post)
Depth-first search.

    @type  graph: graph, digraph
    @param graph: Graph.
    
    @type  root: node
    @param root: Optional root node (will explore only root's connected component)

    @rtype:  tuple
    @return: A tupple containing a dictionary and two lists:
        1. Generated spanning tree
        2. Graph's preordering
        3. Graph's postordering
Depth-first search.
Depth - first search .
def depth_first_search(graph, root=None, filter=null()):
    """
    Depth-first search.

    @type  graph: graph, digraph
    @param graph: Graph.
    
    @type  root: node
    @param root: Optional root node (will explore only root's connected component)

    @rtype:  tuple
    @return: A tupple containing a dictionary and two lists:
        1. Generated spanning tree
        2. Graph's preordering
        3. Graph's postordering
    """
    
    recursionlimit = getrecursionlimit()
    setrecursionlimit(max(len(graph.nodes())*2,recursionlimit))

    def dfs(node):
        """
        Depth-first search subfunction.
        """
        visited[node] = 1
        pre.append(node)
        # Explore recursively the connected component
        for each in graph[node]:
            if (each not in visited and filter(each, node)):
                spanning_tree[each] = node
                dfs(each)
        post.append(node)

    visited = {}            # List for marking visited and non-visited nodes
    spanning_tree = {}      # Spanning tree
    pre = []                # Graph's preordering
    post = []               # Graph's postordering
    filter.configure(graph, spanning_tree)

    # DFS from one node only
    if (root is not None):
        if filter(root, None):
            spanning_tree[root] = None
            dfs(root)
        setrecursionlimit(recursionlimit)
        return spanning_tree, pre, post
    
    # Algorithm loop
    for each in graph:
        # Select a non-visited node
        if (each not in visited and filter(each, None)):
            spanning_tree[each] = None
            # Explore node's connected component
            dfs(each)

    setrecursionlimit(recursionlimit)
    
    return (spanning_tree, pre, post)
def depth_first_search ( graph , root = None , filter = null ( ) ) : recursionlimit = getrecursionlimit ( ) setrecursionlimit ( max ( len ( graph . nodes ( ) ) * 2 , recursionlimit ) ) def dfs ( node ) : """
        Depth-first search subfunction.
        """ visited [ node ] = 1 pre . append ( node ) # Explore recursively the connected component for each in graph [ node ] : if ( each not in visited and filter ( each , node ) ) : spanning_tree [ each ] = node dfs ( each ) post . append ( node ) visited = { } # List for marking visited and non-visited nodes spanning_tree = { } # Spanning tree pre = [ ] # Graph's preordering post = [ ] # Graph's postordering filter . configure ( graph , spanning_tree ) # DFS from one node only if ( root is not None ) : if filter ( root , None ) : spanning_tree [ root ] = None dfs ( root ) setrecursionlimit ( recursionlimit ) return spanning_tree , pre , post # Algorithm loop for each in graph : # Select a non-visited node if ( each not in visited and filter ( each , None ) ) : spanning_tree [ each ] = None # Explore node's connected component dfs ( each ) setrecursionlimit ( recursionlimit ) return ( spanning_tree , pre , post )