36

私はこの問題に多くの時間を費やしてきました。ただし、ツリーの非再帰的な方法でのみ解決策を見つけることができます。ツリーの非再帰的方法、またはグラフの再帰的方法、グラフの再帰的です。

また、多くのチュートリアル (ここではそれらのリンクは提供しません) もアプローチを提供していません。または、チュートリアルが完全に間違っています。私を助けてください。

更新しました：

説明するのは本当に難しいです：

無向グラフがある場合:

   1
 / |  \
4  |   2
    3 /

1-- 2-- 3 --1はサイクルです。

ステップ:「ポップされた頂点の隣人をスタックにプッシュする」では、頂点をプッシュする順序は何ですか?

プッシュされた順序が2、4、の場合3、スタック内の頂点は次のとおりです。

| |
|3|
|4|
|2|    
 _

ノードをポップした後、結果が得られます:1 -> 3 -> 4 -> 2の代わりに1--> 3 --> 2 -->4.

それは間違っています。このシナリオを停止するには、どの条件を追加する必要がありますか?

4

13 に答える 13

49

再帰のない DFS は基本的にBFSと同じですが、データ構造としてキューの代わりにスタックを使用します。

スレッド反復 DFS と再帰 DFS および異なる要素の順序は、両方のアプローチとそれらの違いで処理されます (そして、同じ順序でノードをトラバースすることはありません!)

反復アプローチのアルゴリズムは基本的に次のとおりです。

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)
于 2014-02-02T09:05:21.197 に答える
2

パイソンコード。時間計算量はO ( V + E ) です。ここで、VとEはそれぞれ頂点とエッジの数です。バックトラッキングなしですべての頂点を含むパスが存在する最悪のケース (つまり、検索パスが線形チェーンである) により、空間の複雑さは O( V )です。

スタックは (vertex, vertex_edge_index) の形式のタプルを格納するため、その頂点から処理された最後のエッジの直後のエッジにある特定の頂点から DFS を再開できます (再帰的 DFS の関数呼び出しスタックと同様)。

コード例では、すべての頂点が他のすべての頂点に接続されている完全な有向グラフを使用しています。したがって、グラフはエッジ リスト (グラフGにはすべての頂点が含まれる)であるため、ノードごとに明示的なエッジ リストを格納する必要はありません。

numv = 1000
print('vertices =', numv)
G = [Vertex(i) for i in range(numv)]

def dfs(source):
  s = []
  visited = set()
  s.append((source,None))
  time = 1
  space = 0
  while s:
    time += 1
    current, index = s.pop()
    if index is None:
      visited.add(current)
      index = 0
    # vertex has all edges possible: G is a complete graph
    while index < len(G) and G[index] in visited:
      index += 1
    if index < len(G):
      s.append((current,index+1))
      s.append((G[index], None))
    space = max(space, len(s))
  print('time =', time, '\nspace =', space)

dfs(G[0])

出力：

time = 2000 
space = 1000

ここでの時間はEではなくV操作を測定していることに注意してください。値はnumv *2 です。これは、すべての頂点が 2 回 (検出時と終了時に 1 回) 考慮されるためです。

于 2016-12-15T01:56:54.480 に答える
2

わかった。まだ Java コードを探している場合

dfs(Vertex start){
    Stack<Vertex> stack = new Stack<>(); // initialize a stack
    List<Vertex> visited = new ArrayList<>();//maintains order of visited nodes
    stack.push(start); // push the start
    while(!stack.isEmpty()){ //check if stack is empty
        Vertex popped = stack.pop(); // pop the top of the stack
        if(!visited.contains(popped)){ //backtrack if the vertex is already visited
            visited.add(popped); //mark it as visited as it is not yet visited
            for(Vertex adjacent: popped.getAdjacents()){ //get the adjacents of the vertex as add them to the stack
                    stack.add(adjacent);
            }
        }
    }

    for(Vertex v1 : visited){
        System.out.println(v1.getId());
    }
}
于 2015-07-12T06:51:09.310 に答える
2

再帰は、コール スタックを使用してグラフ トラバーサルの状態を格納する方法です。たとえば、 type のローカル変数を持つことによって、スタックを明示的に使用できますstd::stack。その後、DFS を実装するための再帰は必要ありませんが、ループだけです。

于 2014-02-02T09:04:15.667 に答える
0

Stack を使用し、再帰プロセスでコール スタックによって行われるように実装します。

アイデアは、スタック内の頂点をプッシュし、頂点のインデックスで隣接リストに格納されている頂点に隣接する頂点をプッシュし、グラフ内でさらに移動できなくなるまでこのプロセスを続行することです。グラフを先に進むと、現在スタックの一番上にある頂点を削除します。これは、未訪問の頂点に移動することができないためです。

ここで、スタックを使用して、現在の頂点から探索できるすべての頂点が訪問された場合にのみ、頂点がスタックから削除されるという点を処理します。これは、再帰プロセスによって自動的に行われます。

例えば ​​-

こちらのグラフの例をご覧ください。

( 0 ( 1 ( 2 ( 4 4 ) 2 ) ( 3 3 ) 1 ) 0 ) ( 6 ( 5 5 ) ( 7 7 ) 6 )

上記の括弧は、頂点がスタックに追加され、スタックから削除される順序を示しているため、頂点の括弧は、そこからアクセスできるすべての頂点が完了した場合にのみ閉じられます。

(ここでは隣接リスト表現を使用し、C++ STL を使用してリストのベクトル (ベクトル > AdjList) として実装しました)

void DFSUsingStack() {
    /// we keep a check of the vertices visited, the vector is set to false for all vertices initially.
    vector<bool> visited(AdjList.size(), false);

    stack<int> st;

    for(int i=0 ; i<AdjList.size() ; i++){
        if(visited[i] == true){
            continue;
        }
        st.push(i);
        cout << i << '\n';
        visited[i] = true;
        while(!st.empty()){
            int curr = st.top();
            for(list<int> :: iterator it = AdjList[curr].begin() ; it != AdjList[curr].end() ; it++){
                if(visited[*it] == false){
                    st.push(*it);
                    cout << (*it) << '\n';
                    visited[*it] = true;
                    break;
                }
            }
            /// We can move ahead from current only if a new vertex has been added on the top of the stack.
            if(st.top() != curr){
                continue;
            }
            st.pop();
        }
    }
}
于 2016-07-19T15:18:00.027 に答える
0

これはスペースに関して最適化された DFS だと思います。間違っている場合は訂正してください。

s = stack
s.push(initial node)
add initial node to visited
while s is not empty:
    v = s.peek()
    if for all E(v,u) there is one unvisited u:
        mark u as visited
        s.push(u)
    else 
        s.pop
于 2016-05-28T22:57:37.703 に答える
0

The following Java Code will be handy:-

private void DFS(int v,boolean[] visited){
    visited[v]=true;
    Stack<Integer> S = new Stack<Integer>();
    S.push(v);
    while(!S.isEmpty()){
        int v1=S.pop();     
        System.out.println(adjLists.get(v1).name);
        for(Neighbor nbr=adjLists.get(v1).adjList; nbr != null; nbr=nbr.next){
             if (!visited[nbr.VertexNum]){
                 visited[nbr.VertexNum]=true;
                 S.push(nbr.VertexNum);
             }
        }
    }
}
public void dfs() {
    boolean[] visited = new boolean[adjLists.size()];
    for (int v=0; v < visited.length; v++) {
        if (!visited[v])/*This condition is for Unconnected Vertices*/ {

            System.out.println("\nSTARTING AT " + adjLists.get(v).name);
            DFS(v, visited);
        }
    }
}
于 2016-12-29T06:14:51.213 に答える