すべてのエッジを効率的にトラバースする方法は？

Question

グラフ内のすべてのエッジをトラバースし、繰り返しなしでエッジのコレクションを取得する必要があります。
私はDFSを使用し、次のようにコレクションにエッジを追加し続けます。

procedure DFS(G,v): 
    label v as discovered 
    for all edges from v to w in G.adjacentEdges(v) do 
    { 
      addEdge(v,w);    //get edges 
      if vertex w is not labeled as discovered then 
       recursively call DFS(G,w) 
    } 

が、それはエッジの繰り返しを持っていないはずなので、私は 「addEdges」にいくつかのチェックを行う必要があります。

addEdges(v,w) 
    { 
    if either v or w is not in HashTble(nodes)/
     { 
     add edge(v,w) to collection(edges) 
     add v and w to HashTble(nodes) 
     } 
    else 
     { //both v and w in HashTble(nodes) 
      if edge(v,w) is not in collection(edges) 
      add edge(v,w) to collection(edges) 
     } 
    } 

これが私のやり方です。問題は、グラフが非常に大きく、このグラフ 'addEdges'が時間を消費していることです。これは、コレクション内で何度かチェックインする必要があるためです。

もっと速くできる方法はありますか？ ありがとうございます！

Answer 1

前にエッジを見たことがあるかどうかを確認する必要はありません。ノードを2回訪問しないので、同じエッジを2回（グラフが指示されている場合）にすることはできません。

グラフが無向であれば、すべてのエッジ（u、v）を2回追加します（uを訪れたときとvを訪れたときにもう一度）。このを取り除くために、あなたが唯一のエッジを追加制約を追加することができるかどうかのu < V

アルゴはのようになります。すべてで

すべて：。

procedure DFS(G,v): 
label v as discovered 
for all edges from v to w in G.adjacentEdges(v) do 
{ 
     add edge(v,w) to output edges 
     if vertex w is not labeled as discovered then 
      recursively call DFS(G,w) 
} 

それとも、無向グラフを持っている場合：

procedure DFS(G,v): 
label v as discovered 
for all edges from v to w in G.adjacentEdges(v) do 
{ 
     if (v < w) add edge(v,w) to output edges 
     if vertex w is not labeled as discovered then 
      recursively call DFS(G,w) 
} 

は `for`ループの外のラベル試験のための` if`を動かし