DFS對於有向圖而不是BST有何意義？

我正在更好地理解深度優先搜索算法的應用。我明白如何使用它遍歷二叉搜索樹來生成一個排序列表。我的Python實現如下所示：DFS對於有向圖而不是BST有何意義？

class bst_node: 
    def __init__(self, x): 
     self.x  = x 
     self.left = None 
     self.right = None   

def get_dfs_path(bst_node): 
    """ Returns a depth-first search path for a BST """ 

    left = [] if bst_node.left == None else get_dfs_path(bst_node.left) 
    right = [] if bst_node.right == None else get_dfs_path(bst_node.right) 

    return left + [bst_node] + right

其中的工作非常好。然而，我很難理解這種算法是否可以有效地應用於一個有向圖，而不是更嚴格的BST。考慮下面的有向圖節點的實現：

class di_node: 
    def __init__(self, x): 
     self.x = x 
     self.visited = False 
     self.children = []

因爲在有向圖中的節點可以有孩子的任意數，DFS邏輯不能簡單地構建路徑dfs_path(left) + parent_node + dfs_path(right)。有人可以幫助我理解dfs如何適用於有向圖嗎？

編輯

好吧，基於響應讓我嘗試DFS遍歷一個di_node。請讓我知道，如果我在任何地方接近該商標：

def get_dfs_path(di_node): 
    """ Returns a depth-first search path for a digraph """ 
    if di_node.visited: 
     return [] 
    else: 
     di_node.visited = True 
     return [di_node] + [ get_dfs_path(child) for child in di_node.children) ]

來源

2012-02-11 Stephen Gross

而不是隻是採取左側，然後正確的孩子，你得到的兒童名單，並按順序通過他們，忽略被標記爲訪問的那些。（並且在您訪問它們時將節點標記爲已訪問。） – bdares 2012-02-11 17:07:30

@bdares是正確的。使用兒童名單通常是這種方法。就像一棵樹，但不完全一樣。 – Justin 2012-02-11 17:10:51

@bdares你能確認我的編輯是否正確嗎？ – 2012-02-11 17:49:05