12

さて、これは私がしばらく読んでいるStack Overflowに関する私の最初の投稿であり、このサイトを本当に賞賛しています。これが受け入れられるものになることを願っています。ですから、私はアルゴリズム入門（Cormen。MIT Press）をずっと読んでいて、グラフアルゴリズムに取り組んでいます。私は、幅と深さ優先探索のためにレイアウトされた正式なアルゴリズムを非常に詳細に研究してきました。

深さ優先探索用に指定された疑似コードは次のとおりです。

DFS(G)
-----------------------------------------------------------------------------------
1  for each vertex u ∈ G.V
2      u.color ← WHITE       // paint all vertices white; undiscovered
3      u.π ← NIL
4      time ← 0              // global variable, timestamps
5  for each vertex u ∈ G.V
6      if u.color = WHITE
7          DFS-VISIT(G,u)

DFS-VISIT(G, u)
-----------------------------------------------------------------------------------
1  u.color ← GRAY          // grey u; it is discovered
2  time ← time + 1 
3  u.d ← time
4  for each v ∈ G.Adj[u]   // explore edge (u,v)
5      if v.color == WHITE
6          v.π ← u
7          DFS-VISIT(G,v) 
8  u.color ← BLACK         // blacken u; it is finished
9  time ← time + 1
10 u.f ← time

このアルゴリズムは再帰的であり、複数のソースから進行します（接続されていないグラフのすべての頂点を検出します）。これには、ほとんどの言語固有の実装で省略される可能性のあるいくつかのプロパティがあります。頂点の3つの異なる「色」を区別します。最初はすべてを白で塗りつぶし、次に「発見」されると（DFS-VISITでアクセス）、灰色で塗りつぶされます。DFS-VISITアルゴリズムは、現在の頂点の隣接リストで自分自身を再帰的に呼び出すループを実行し、白いノードへのエッジがなくなったときにのみ頂点を黒く塗りつぶします。

また、各頂点の他の2つの属性は維持されます。udとufは、頂点が検出されたとき（灰色に塗られた）または頂点が終了したとき（黒に塗られた）までのタイムスタンプです。ノードが最初にペイントされるとき、そのノードには1のタイムスタンプがあり、別のノードがペイントされるたびに（灰色か黒か）、次の整数値にインクリメントされます。u.πも維持されます。これは、uが検出されたノードへの単なるポインタです。

Algorithm Non-Recursive-DFS(G)
-----------------------------------------------------------------------------------
1   for each vertex u ∈ G.V
2       u.color ← WHITE
3       u.π ← NIL
4   time = 0
5   for each vertex u ∈ G.V
6       if u.color = WHITE
7           u.color ← GRAY
8           time ← time + 1
9           u.d ← time
7           push(u, S)
8           while stack S not empty
9               u ← pop(S)
10              for each vertex v ∈ G.Adj[u]
11                  if v.color = WHITE
12                      v.color = GRAY
13                      time ← time + 1
14                      v.d ← time
15                      v.π ← u
16                      push(v, S)
17              u.color ← BLACK 
18              time ← time + 1
19              u.f ← time

* EDIT 10/31/12 *これは、私のアルゴリズムが長い間正しくないことを恥ずかしく思います。ほとんどの場合は機能しますが、すべてではありません。質問に対して人気のある質問バッジを取得しました。Irfyが以下の回答で問題を見つけた場所を確認したので、そこにクレジットが表示されます。将来これを必要とする人のために、ここで修正しています。

上記のアルゴリズムに欠陥がある人はいますか？私はグラフ理論の専門家ではありませんが、再帰と反復についてはかなりよく理解していると思います。これも同じように機能するはずです。私はそれを再帰的アルゴリズムと機能的に同等にすることを目指しています。必要がない場合でも、最初のアルゴリズムのすべての属性を維持する必要があります。

私がそれを書き始めたとき、私は私が三重のループを持っているとは思いませんでした、しかしそれはそれが判明した方法です。Googleを見回したときに、二重にネストされたループしかない他の反復アルゴリズムを見たことがありますが、それらは複数のソースから進んでいるようには見えません。（つまり、接続されていないグラフのすべての頂点を検出するわけではありません）

4

8 に答える 8

6

どちらのアルゴリズムでも問題ありません。2つ目は、再帰からスタックベースへの直接変換です。すべての変異状態はスタックに保存されます。Gアルゴリズムの実行中に変更されることはありません。

アルゴリズムは、アルゴリズムが各ノードを訪問した順序に基づいて、切断された領域ごとにスパニングツリーを生成します。ツリーは、親ノード（u.π）への参照とセグメントツリー（u.dおよびu.f）の両方で表されます。

子には、親ノードへの参照（またはNULLルートの場合）があり、その範囲（child.d .. child.f）が親の範囲内に含まれています。

parent.d < child.d < child.f < parent.f

child.π = parent

編集：私は翻訳に間違いを見つけました。実際に現在の状態をスタックにプッシュするのではなく、将来のメソッド引数をプッシュします。さらに、ポップされたノードに色を付けたり、フィールドGRAYを設定したりすることはありません。f

これは、元の最初のアルゴリズムの書き直しです。

algorithm Stack-DFS(G)
    for each vertex u ∈ G.V
        u.color ← WHITE
        u.π ← NIL
    time ← 0
    S ← empty stack
    for each vertex u ∈ G.V
        if u.color = WHITE
            # Start of DFS-VISIT
            step ← 1
            index ← 0
            loop unconditionally
                if step = 1
                    # Before the loop
                    u.color ← GRAY
                    time ← time + 1
                    u.d ← time
                    step ← 2
                if step = 2
                    # Start/continue looping
                    for each vertex v ∈ G.Adj[u]
                        i ← index of v
                        if i ≥ index and v.color = WHITE
                            v.π ← u
                            # Push current state
                            push((u, 2, i + 1), S)
                            # Update variables for new call
                            u = v
                            step ← 1
                            index ← 0
                            # Make the call
                            jump to start of unconditional loop
                    # No more adjacent white nodes
                    step ← 3
                if step = 3
                    # After the loop
                    u.color ← BLACK
                    time ← time + 1
                    u.right ← time
                    # Return
                    if S is empty
                        break unconditional loop
                    else
                        u, step, index ← pop(S)

おそらく最適化できる場所がいくつかありますが、少なくとも今は機能するはずです。

結果：

Name   d    f   π
q      1   16   NULL
s      2    7   q
v      3    6   s
w      4    5   v
t      8   15   q
x      9   12   t
z     10   11   x
y     13   14   t
r     17   20   NULL
u     18   19   r
于 2012-04-26T23:10:14.917 に答える
1 
int stackk[100];
int top=-1;
void graph::dfs(int v){
 stackk[++top]=v;
// visited[v]=1;
 while(top!=-1){
   int x=stackk[top--];
   if(!visited[x])
    {visited[x]=1;
     cout<<x<<endl;
    }
   for(int i=V-1;i>=0;i--)
   {
        if(!visited[i]&&adj[x][i])
        {   //visited[i]=1;
            stackk[++top]=i;
        }
   }
 }
}
void graph::Dfs_Traversal(){
 for(int i=0;i<V;i++)
  visited[i]=0;
 for(int i=0;i<V;i++)
  if(!visited[i])
    g.dfs(i);
于 2013-12-31T16:46:29.840 に答える
1

はるかに単純な擬似コードを書くことができたと思います。

しかし、最初に、物事を少し明確にするためのいくつかのコメント：

  1. v.pDescendant-隣接リストによって指定された頂点の子孫へのポインタ。
  2. 隣接リストでは、各要素にリンクリストの次の要素を指すフィールド「pNext」があると想定しました。
  3. ポインタとは何かを強調するために、主に「->」と「＆」などのC++構文を使用しました。
  4. Stack.top（）は、スタックの最初の要素へのポインターを返します。ただし、pop（）とは異なり、削除されません。

アルゴリズムは、次の観察に基づいています。訪問すると、頂点がスタックにプッシュされます。すべての子孫の調査（黒化）が完了した場合にのみ、削除（ポップ）されます。

DFS(G)
1. for all vertices v in G.V do
2.   v.color = WHITE; v.parent = NIL; v.d = NIL; v.f = NIL; v.pDescendant = adj[v].head
3. time = 0 
4. Initialize Stack
5. for all vertices v in G.V s.t. v.color == WHITE do
6.   time++
7.   Stack.push(&v)
8.   v.color = GRAY 
9.   v.d = time 
10.   DFS-ITERATIVE(G,v)

DFS-ITERATIVE(G,s) 
1. while Stack.Empty() == FALSE do
2.   u = Stack.top();
3.   if u.pDescendant == NIL // no Descendants to u || no more vertices to explore
4.      u.color = BLACK
5.      time++
6.      u.f = time
7.      Stack.pop()
8.   else if (u.pDescendant)->color == WHITE
9.      Stack.push(u.pDescendant)
10.     time++
10.     (u.pDescendant)->d = time
11.     (u.pDescendant)->color = GRAY
12.     (u.pDescendant)->parent = &u
12.     u.pDescendant= (u.pDescendant)->pNext // point to next descendant on the adj list      
13.  else
14.     u.pDescendant= (u.pDescendant)->pNext // not sure about the necessity of this line
于 2015-04-05T18:26:38.280 に答える
0

これがC++のコードです。

class Graph
{
    int V;                          // No. of vertices
    list<int> *adj;                 // Pointer to an array containing adjacency lists
public:
    Graph(int V);                    // Constructor
    void addEdge(int v, int w);             // function to add an edge to graph
    void BFS(int s);                    // prints BFS traversal from a given source s
    void DFS(int s);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V]; //list of V list
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}


  void Graph::DFS(int s)
        {
                 //mark unvisited to each node
        bool *visited  = new bool[V];
        for(int i = 0; i<V; i++)
            visited[i] =false;
        int *d = new int[V];  //discovery
        int *f = new int[V]; //finish time

        int t = 0;       //time

        //now mark current node to visited
        visited[s] =true;
        d[s] = t;            //recored the discover time

        list<int> stack;

        list<int>::iterator i;

        stack.push_front(s);
        cout << s << " ";

        while(!(stack.empty()))
        {
            s= stack.front();
            i = adj[s].begin();

            while ( (visited[*i]) && (i != --adj[s].end()) )
            {
                ++i;
            }
            while ( (!visited[*i])  )
            {

                visited[*i] =true;
                t++;
                d[*i] =t;
                if (i != adj[s].end())
                    stack.push_front(*i);

                cout << *i << " ";
                i = adj[*i].begin();

            }

            s = stack.front();
            stack.pop_front();
            t++;
            f[s] =t;

        }
        cout<<endl<<"discovery time of the nodes"<<endl;

        for(int i = 0; i<V; i++)
        {
            cout<< i <<" ->"<< d[i] <<"    ";
        }
        cout<<endl<<"finish time of the nodes"<<endl;

        for(int i = 0; i<V; i++)
        {
            cout<< i <<" ->"<< f[i] <<"   ";
        }

    }

         int main()
         {
        // Create a graph given in the above diagram
        Graph g(5);
        g.addEdge(0, 1);
        g.addEdge(0, 4);
        g.addEdge(1, 4);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(3, 4);
        g.addEdge(2, 3);


        cout << endl<<"Following is Depth First Traversal (starting from vertex 0) \n"<<endl;
        g.DFS(0);

        return 0;
    }

単純な反復DFS。また、発見時間と終了時間を確認できます。疑問がある場合はコメントしてください。コードを理解するのに十分なコメントを含めました。

于 2014-02-20T13:46:04.470 に答える
-1

非再帰的なコードに重大な欠陥があります。

であるかどうかを確認した後、プッシュする前にマークを付けることvはありません。そのため、他の未訪問のノードから何度も表示され、そのノードへの複数の参照がスタックにプッシュされる可能性があります。これは潜在的に壊滅的な欠陥です（無限ループなどを引き起こす可能性があります）。WHITEGRAYWHITEv

.dまた、ルートノード以外は設定しません。これは、入れ子集合モデルの属性.dsと.fsが正しくないことを意味します。.d（ sとsが何であるかわからない場合.fは、その記事を読んでください。当時、私には非常に啓発的でした。記事leftはあなたのもの.dでrightあり、あなたのもの.fです。）

基本的に、内部は外部からループを除いたものifと同じである必要があり、さらに親参照が必要です。ifあれは：

11                  if v.color = WHITE
++                      v.color ← GRAY
++                      time ← time + 1
++                      v.d ← time
12                      v.π ← u
13                      push(v, S)

それを修正すれば、それは真に同等であるはずです。

于 2012-04-26T22:41:42.570 に答える
-1

非再帰バージョンでは、再帰スタックの状態を反映する別の色が必要です。したがって、ノードのすべての子がスタックにプッシュされたことを示すために、color=REDを追加します。また、スタックにpeek（）メソッドがあると仮定します（そうでなければ、ポップと即時プッシュでシミュレートできます）

したがって、その追加により、元の投稿の更新バージョンは次のようになります。 

for each vertex u ∈ G.V
      u.color ← WHITE
      u.π ← NIL
  time = 0
  for each vertex u ∈ G.V
      if u.color = WHITE
          u.color ← GRAY
          time ← time + 1
          u.d ← time
          push(u, S)
          while stack S not empty
              u ← peek(S)
              if u.color = RED
                  //means seeing this again, time to finish
                  u.color ← BLACK
                  time ← time + 1
                  u.f ← time
                  pop(S) //discard the result
              else
                  for each vertex v ∈ G.Adj[u]
                     if v.color = WHITE
                         v.color = GRAY
                         time ← time + 1
                         v.d ← time
                         v.π ← u
                         push(v, S)
                   u.color = RED
于 2013-05-19T12:18:52.023 に答える
-1 
I used Adjacency Matrix:    

void DFS(int current){
        for(int i=1; i<N; i++) visit_table[i]=false;
        myStack.push(current);
        cout << current << "  ";
        while(!myStack.empty()){
            current = myStack.top();
            for(int i=0; i<N; i++){
                if(AdjMatrix[current][i] == 1){
                    if(visit_table[i] == false){ 
                        myStack.push(i);
                        visit_table[i] = true;
                        cout << i << "  ";
                    }
                    break;
                }
                else if(!myStack.empty())
                    myStack.pop();
            }
        }
    }
于 2013-08-17T12:39:14.450 に答える
-2

再帰バージョンとスタックバージョンが機能的に同等ではないケースが少なくとも1つあると思います。三角形の場合を考えてみましょう。頂点A、B、Cが相互に接続されています。ここで、再帰DFSを使用すると、ソースAで取得される先行グラフはA->B->CまたはA->C->Bのいずれかになります（A-> Bは、Aが深さBの親であることを意味します最初の木）。

ただし、スタックバージョンのDFSを使用する場合、BとCの両方の親は常にAとして記録されます。Bの親がCである場合、またはその逆の場合はあり得ません（再帰DFSの場合は常にそうです）。 ）。これは、任意の頂点（ここではA）の隣接リストを探索するときに、隣接リスト（ここではBとC）のすべてのメンバーを一度にプッシュするためです。

グラフ内のアーティキュレーションポイントを見つけるためにDFSを使用しようとすると、これが関連する可能性があります[1]。1つの例は、再帰バージョンのDFSを使用する場合にのみ、次のステートメントが当てはまるというものです。

ルート頂点は、深さ優先ツリーに少なくとも2つの子がある場合にのみ、アーティキュレーションポイントになります。

三角形では、明らかにアーティキュレーションポイントはありませんが、スタックDFSは、深さ優先ツリーの任意のソース頂点に対して2つの子を提供します（Aには子BとCがあります）。上記のステートメントが当てはまるのは、再帰的DFSを使用して深さ優先ツリーを作成する場合のみです。

[1]アルゴリズムの概要、CLRS-問題22-2（第2版および第3版）

于 2013-02-01T16:21:37.733 に答える