12

好的，这是我在 Stack Overflow 上的第一篇文章，我已经阅读了一段时间，非常欣赏这个网站。我希望这是可以接受的问题。因此，我一直在阅读 Intro to Algorithms (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 算法运行一个循环，在当前顶点的邻接列表上递归地调用自身，并且仅当顶点没有到任何白色节点的边时才将顶点绘制为黑色。

每个顶点的另外两个属性也被维护 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

* 编辑 2012 年 10 月 31 日 *很尴尬，我的算法已经错误了这么久，它在大多数情况下都可以工作，但不是全部。我刚刚为该问题获得了一个受欢迎的问题徽章，我看到 Irfy 在下面的答案中发现了问题，所以这就是功劳所在。我只是在这里为将来需要它的任何人修复它。

有人看到上述算法的缺陷吗？到目前为止，我还不是图论方面的专家，但我认为我对递归和迭代有很好的掌握，我相信这应该也是一样的。我希望使它在功能上等同于递归算法。即使不需要，它也应该保留第一个算法的所有属性。

当我开始写它时，我不认为我会有一个三重循环，但结果就是这样。当我环顾谷歌时，我看到了其他只有双重嵌套循环的迭代算法，但是，它们似乎并没有从多个来源进行。（即他们不会发现未连接图的每个顶点）

4

8 回答 8

6

两种算法都很好。第二个是从递归到基于堆栈的直接转换。所有变异状态都存储在堆栈中。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

我想我设法编写了一个更简单的伪代码。

但首先要说几句让事情变得更清楚：

  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 回答
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 回答
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

在非递归版本中，我们需要另一种颜色来反映递归堆栈中的状态。因此，我们将添加一个 color=RED 来指示该节点的所有子节点都被推入堆栈。我还将假设堆栈有一个 peek() 方法（否则可以用 pop 和立即推送来模拟）

因此，添加后原始帖子的更新版本应如下所示： 

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 回答
-1

您的非递归代码确实存在严重缺陷。

检查是否v为 is后WHITE，在 push 之前从未标记它GRAY，因此它可能会被视为WHITE一次又一次来自其他未访问的节点，从而导致对该v节点的多次引用推入堆栈。这可能是一个灾难性的缺陷（可能导致无限循环等）。

.d此外，除了根节点之外，您不进行设置。这意味着嵌套集模型属性.ds 和.fs 将不正确。（如果您不知道.ds 和.fs 是什么，请阅读那篇文章，当时对我很有启发。这篇文章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 回答
-2

我相信至少有一种情况是递归和堆栈版本在功能上不等效。考虑三角形的情况 - 顶点 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]。一个例子是，仅当我们使用 DFS 的递归版本时，以下语句才成立。

当且仅当它在深度优先树中至少有两个孩子时，根顶点才是一个关节点。

在三角形中，显然没有关节点，但 stack-DFS 仍然为深度优先树中的任何源顶点提供两个孩子（A 有孩子 B 和 C）。只有当我们使用递归 DFS 创建深度优先树时，上述陈述才成立。

[1] 算法简介，CLRS - 问题 22-2（第二版和第三版）

于 2013-02-01T16:21:37.733 回答