グラフ内のエッジを訪問する

Question

私はDFSアルゴリズムを使用していて、各エッジを訪問したとマークしたいと考えています。ノードを探してそれをいくつかのセンチネルに置き換える方法がありますが、検索したノードに対応する値を格納すると、ルックアップ時間が長くなります。行列は多くの領域を消費します。そうするための最良のアルゴリズムは何ですか？

Answer 1

頂点ペアのセットを維持するだけで済みます。例：Java HashMap<Pair<Vertex, Vertex>>。 Pythonでは、2要素タプルのSetがあります。

発見されたばかりの新しい頂点の子孫を列挙し、それらをDFSスタックに追加すると、エッジの訪問が発生します。再帰DFSを使用している場合は、各子孫に対して再帰呼び出しを行うようになります。スタックバージョンは次のとおりです：

dfs(graph) 
    visitedVertices = \emptyset 
    visitedEdges = \emptyset 
    // Try all vertices as search roots 
    for each vertex r in graph 
    push r onto empty stack 
    while notEmpty(stack) 
     u = pop stack 
     if u not in visitedVertices 
     add u to visitedVertices 
     foreach v such that u->v is in graph 
      add (u,v) to visitedEdges // Visit the edge 
      push v on stack 

これは、私はあなたがこれをしたい理由はわかりません。正しく実装されたDFSは、自然に各エッジを1回だけ横断します。上記のアルゴリズムを見て、これを自分自身に証明することができます。 (u,v)の訪問は、uが以前に訪れたことがない場合にのみ可能です。

おそらく、あなたは、検索の進行状況を見ているか、実際にあなたが訪問したときにエッジに他の情報を追加している他のスレッドがありますか？