BSTではなく、有向グラフでDFSはどのように意味がありますか？

Question

私は、深さ優先探索アルゴリズムの応用をよりよく理解するために取り組んでいます。バイナリ検索ツリーをトラバースしてソートされたリストを作成する方法を理解しています。私のPythonの実装は次のようになります。

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ではなく一般的に有向グラフに有意義に適用できるかどうかを理解するのには苦労しています。有向グラフ内のノードは、子供の任意の数を有することができるので、DFSロジックは単にdfs_path(left) + parent_node + dfs_path(right)としてパスを構築することができない

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

次有向グラフノードの実装を考えます。どのようにdfsが有向グラフに適用されるかを/私が理解するのを助けることができますか？応答に基づいて[OK]を

EDIT

は、私がdi_nodeのためのDFS横断を試みてみましょう。

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) ] 

Answer 1

ノードが2つ以上のサブツリーを持つことができるので、順序通りのトラバース（左のサブツリー、現在のノード、右のサブツリー）は一般的なグラフにはあまり意味がありません。しかし、深さのある最初の検索では、プリオーダー（現在のノードを最初に処理し、その後にサブツリー）またはポストオーダー（最初にサブツリーを処理し、現在のノードを処理する）を使用することもできます。これらの2つはグラフでうまく動作します。

グラフ上でDFSを実行する際には、すでに訪れたノードを把握しておく必要があります。さもなければ、循環グラフをトラバースするときに無限ループを得るでしょう。

Answer 2

DFSをグラフで使用してサイクルを検出することができます。訪問したノードを追跡し、すでに訪問したノードにアクセスした場合は、サイクルが検出されています。