使用DFS进行无递归的拓扑排序

Question

我知道常见的拓扑排序方法是使用DFS和递归。但是如果使用stack<int>而不是递归，你该如何做呢？我需要获取反向后序，但现在有些困惑：

图是一个vector<vector<int>>邻接表

以下是我想用于拓扑排序的DFS:

bool visited[MAX]={0};
stack<int> dfs, postOrder;
vector<int> newVec;
vector<int>::iterator it;

for(int i=0;i<MAX;i++){
    if(visited[i]==false){
        dfs.push(i);
    }   
    while(!dfs.empty()){
        int node=dfs.top();
        dfs.pop();
        visited[node]=true;
        newVec=graph[node]; //vector of neighboors
        for(it=newVec.begin();it!=newVec.end();it++){
            int son=*it;
            if(visited[son]==false){
                dfs.push(son);
            }
        }
    }
}

- fersarr

Answer 1

为了构造postOrder列表，您需要知道算法何时完成处理节点k的最后一个子节点的时间。

一种确定何时从栈中弹出最后一个子节点的方法是在栈上放置特殊标记以指示某个节点的子节点开始的位置。您可以将dfs堆栈的类型更改为vector<pair<bool,int>>。当bool设置为true时，表示它是一个父节点；false表示它是一个子节点。

当您从堆栈中弹出“子对”（即第一成员设为false的对）时，您运行目前的代码，即使用for循环将它们的所有子节点都推入堆栈中。但是，在进入for循环之前，您应该先将make_pair(true, node)推入堆栈，以标记此node的所有子节点的开头。

当您从堆栈中弹出“父对”时，您将父索引推入postOrder，然后继续：

vector<vector<int> > graph;
vector<bool> visited(max);
stack<pair<bool,int>> dfs;
stack<int> postOrder;
for(int i=0 ; i < max ; i++){
    if(!visited[i]){
        dfs.push(make_pair(false,i));
    }   
    while(!dfs.empty()){
        pair<bool,int> node=dfs.top();
        dfs.pop();
        if (node.first) {
            postOrder.push(node.second);
            continue;
        }
        if (visited[node.second]) {
            continue;
        }
        visited[node.second]=true;
        dfs.push(make_pair(true, node.second));
        const auto& newVec=graph[node.second]; //vector of neighboors
        for(const auto son: newVec){
            if(!visited[son]){
                dfs.push(make_pair(false, son));
            }
        }
    }
}

在 ideone 上的演示。

- Sergey Kalinichenko

---

如果你只在弹出节点时才“访问”它们，那么你是否会得到所需的DFS？对此，你只需要一个单独的堆栈，就像原帖中所述。 （而通过“访问”，我指的是对节点进行操作，而不是设置“visited = true”。这一点你必须在“push”时完成。） - Joe Z

@JoeZ 为了进行拓扑排序，你需要知道何时完成对一个节点的最后一个子节点的处理。当你从栈中弹出一个节点时，你知道你正在开始处理该节点的第一个子节点；这时候宣布该节点为“已访问”还为时过早。 - Sergey Kalinichenko

当我运行算法时，即使没有反向边，它也给出了具有重复值的拓扑排序。考虑一个标记为1、2、3...100的顶点图。每个顶点都有6条边。对于顶点1，六条边将连接到2、3、4、5、6、7。当我尝试进行拓扑排序时，它给出了重复的值。这里有一个演示：ideone.com/FJfwgB。你如何使得反向边不会在后序中导致重复的值？ - AlwaysNull

算法中存在一个错误 - 如果你创建的图形是 vector<vector<int> > graph { {1, 2, 3}, {3}, {1, 3}, {}};，那么你将得到访问顺序 3, 1, 2, 1, 0 => 1 被访问了两次，但实际上只应该访问一次。 - Martin Perry

@MartinPerry 谢谢！这是因为我在进入 while 循环之前没有检查 visited。现在已经修复了。 - Sergey Kalinichenko

Answer 2

我认为你的代码是一个很好的非递归DFS。拓扑排序的关键点在于：

当你选择将一个节点压入栈中时，这个节点必须没有前驱（即度数为0）。这意味着你要基于入度进行DFS，而不是将所有相邻的节点都压入栈中，你总是选择度数为0的节点。

所以你要将所有没有前驱的节点都压入栈中。弹出其中一个，打印它并从所有相邻节点的前驱列表中删除它（或将其相邻节点的入度减1）。这需要你编辑你的相邻列表。然后将现在入度为0的所有相邻节点都推入栈中（这个阶段可能会失败，但没关系，你仍然有一些节点在栈中）。然后弹出下一个节点。重复此过程直到栈为空。你打印的节点序列就是图的拓扑排序结果。

- Archeosudoerus

---

看起来它会工作，但我需要添加一个额外的步骤来找到入度为零的那些，对吗？ - fersarr

是的，不要忘记修改您从堆栈中弹出的节点的相邻节点的入度。将它们减去1。 - Archeosudoerus

据我所知，这被称为Kahn算法来达到拓扑排序。我认为它的效率较低，因为在每次迭代中，您需要知道哪些节点具有0入边。 - Enosh Cohen

Answer 3

迭代拓扑排序。使用堆栈和颜色标记图节点：0-未访问，1-正在进行，2-已完成。内置检查图是否有环的功能。这种方法不需要在堆栈中添加额外状态（如此解决方案）来确定我们是否应将当前节点添加到答案中。请尝试样例。

void dfs(const unordered_multimap<int, int>& graph, vector<int>& color, int node, const function<void(int)> post_order_func)
{
  stack<int> nodes;
  nodes.push(node);

  while (!nodes.empty())
  {
    int from = nodes.top();

    if (color[from] == 1)
    {
      color[from] = 2;
      post_order_func(from);
      nodes.pop();
      continue;
    }
    else if (color[from] == 2)
    {
      nodes.pop();
      continue;
    }

    color[from] = 1;
    auto range = graph.equal_range(from);

    for (auto it = range.first; it != range.second; ++it)
    {
      const auto& to = it->second;
      if (color[to] == 0)
      {
        nodes.push(to);
      }
      else if (color[to] == 1)
      {
        throw runtime_error("Graph has cycle. Topological sort impossible.");
      }
    }
  }
}

void topological_sort(int n, const unordered_multimap<int, int>& graph, vector<int>& result)
{
  result.resize(n);

  vector<int> color(n, 0);
  int j = 0;
  auto post_order_func = [&result, &j](int node) {
    result[j++] = node;
  };

  for (int i = 0; i < n; ++i)
  {
    if (color[i] == 0)
    {
      dfs(graph, color, i, post_order_func);
    }
  }

  reverse(begin(result), end(result));
}

- Ctrl

Answer 4

我对C++不是很熟悉，所以我用JAVA来回答问题。

给出的答案也是LeetCode 210问题的解决方案。

在DFS的迭代方法中，当节点u的所有邻居都已经被访问过时，我们进行回溯，因此我们将弹出堆栈元素并将其推入拓扑排序堆栈。

 class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            // Create graph
            Graph g = new Graph(numCourses);
            for(int i = 0; i < prerequisites.length; i++) {
                g.addEdge(prerequisites[i][1], prerequisites[i][0]);
            }
       
        // Detect Cycle
        if(g.isCycleExist()) {
            return new int[0];
        }
        
        // Apply Topological Sort
        Stack<Integer> stack = new Stack<Integer>();
        boolean[] visited = new boolean[numCourses];
        // apply dfs
        for(int i = 0; i < numCourses; i++) {
            if(!visited[i]) {
                g.iterativeDFS(i, visited, stack);
            }
        }
        int[] ans = new int[numCourses];
        int i = 0;
        while(!stack.empty()) {
            ans[i++] = stack.pop();
        }
        return ans;
    }
}


class Graph {
    private int v;
    private LinkedList<Integer> addList[];

    Graph(int vertices) {
        v = vertices;
        addList = new LinkedList[vertices]; 
        for(int i=0; i < vertices; i++) {
            addList[i] = new LinkedList<Integer>();
        }
    }

    void addEdge(int source, int destination) {
        addList[source].add(destination);
    }
    
    boolean isCycleExist() {
        int[] visited = new int[v];
        for(int u = 0; u < v; u++){
            if(visited[u] == 0) {
                if(isCycleUtil(u, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    boolean isCycleUtil(int u, int[] visited) {
        if(visited[u] == 1) { // already visited
            return true; // if we comes to a node which is in process that means its a loop.
        }
        if(visited[u] == 2) { // already processed
            return false; // as it is already procedd no need to procedd it again.
        }
        visited[u] = 1;   // Mark current as visited
        for(int v = 0; v < this.addList[u].size(); v++) {
                if(isCycleUtil(this.addList[u].get(v), visited)){
                    return true;
                }
        }
        visited[u] = 2; // Mark current node as processed
        return false;
    }
    
    void dfs(int u, boolean[] visited, Stack<Integer> stack) {
        visited[u] = true;
        for(int v=0; v< addList[u].size(); v++) {
            if(!visited[addList[u].get(v)]) {
                dfs(addList[u].get(v), visited, stack);
            }
        }
        stack.push(u);
    }
    
    void iterativeDFS(int i, boolean[] visited, Stack<Integer> topologicalStack) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(i);
        visited[i] = true;
        while(!stack.empty()) {
            int u = stack.peek();
             boolean isAllVisited = true;
             for(int v=0; v< addList[u].size(); v++) {
                if(!visited[addList[u].get(v)]) {
                    isAllVisited = false;
                    visited[addList[u].get(v)] = true;
                    stack.push(addList[u].get(v));
                    break;
                }
            }
            if(isAllVisited) {
                int x = stack.pop();
                topologicalStack.push(x);
            }
        }
    }
        
}

- Pulkit Aggarwal

Answer 5

该节点为第一次访问并处于处理中，被添加到堆栈中作为false。这些节点将按照LIFO顺序从堆栈进行处理，并更改为true（已处理表示已访问其子节点）。在处理完所有子节点后，沿着路径返回时，此节点将从堆栈中删除。

对于那些试图实现此代码的人，visited[node.second]=true; 应该移动到第一次将节点添加到堆栈作为false的2个位置。这样，可以避免回溯到已经遍历过的顶点的反向边重复访问。

- Atif Hussain

Answer 6

图的结构如下：

N：顶点数 adj[]：输入图

vector<int> topoSort(int V, vector<int> adj[]) {
    stack<int> s;
    vector<int> f(V,0);
    
    stack<int> out; 
    int i,j,x;
    for(i=0;i<V;i++){
        if(f[i]==0){
            s.push(i);
            
            while(!s.empty()){
                x = s.top();
                s.pop();
                if(f[x]==1){
                    out.push(x);
                    continue;
                }
                f[x] = 1;
                s.push(x);
                for(j=0;j<adj[x].size();j++){
                    if(f[adj[x][j]]==0){
                        s.push(adj[x][j]);
                    }
                }
            }
        }
    }
    
    vector<int> output;

    while(!out.empty()){
        x=out.top();
        out.pop();
        //cout << x << " ";
        output.push_back(x);
    }
    //cout << endl;
    
    return output;
}

- H Soora

Answer 7

这是Java中非递归方式进行拓扑排序的代码。它或多或少类似于DFS方法，但还有一些额外的代码来达到目标。

package com.adjacency.list;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node {
    public int data;
    public Node link;

    @SuppressWarnings("unused")
    private Node() {
    }

    public Node(int data) {
        this.data = data;
        this.link = null;
    }
}

class AdjacencyList {
    public Node head;

    public AdjacencyList() {
        head = null;
    }
}

public class Graph {
    private AdjacencyList[] adjacencyArray;
    private int numberOfVertices;

    boolean visited[];

    @SuppressWarnings("unused")
    private Graph() {
    }

    public Graph(int numberOfVertices) {
        this.numberOfVertices = numberOfVertices;
        this.adjacencyArray = new AdjacencyList[this.numberOfVertices];

        for (int index = 0; index < this.numberOfVertices; ++index) {
            this.adjacencyArray[index] = new AdjacencyList();
        }

        visited = new boolean[this.numberOfVertices];
    }

    public void addEdge(int fromVertex, int toVertex) {
        Node node = new Node(toVertex);

        if (adjacencyArray[fromVertex].head == null) {
            adjacencyArray[fromVertex].head = node;
        } else {
            node.link = adjacencyArray[fromVertex].head;
            adjacencyArray[fromVertex].head = node;
        }
    }

    private boolean hasNonVisitedNeighbour(int data) {
        Node iterator = adjacencyArray[data].head;
        while (iterator != null) {
            if (!visited[iterator.data]) {
                // System.out.println("Non visited node present");
                return true;
            }
            iterator = iterator.link;
        }
        return false;
    }

    private int nextNonVisitedNeighbour(int data) {
        Node iterator = adjacencyArray[data].head;
        while (iterator != null) {
            if (!visited[iterator.data]) {
                return iterator.data;
            }
            iterator = iterator.link;
        }
        return -1;
    }

    public void topologicalSort() {
        for (int index = 0; index < numberOfVertices; ++index) {
            visited[index] = false;
        }

        Stack<Integer> output = new Stack<Integer>();
        Stack<Integer> stack = new Stack<Integer>();

        for (int nodeInSequence = 0; nodeInSequence < numberOfVertices; ++nodeInSequence) {
            if (!visited[nodeInSequence]) {
                visited[nodeInSequence] = true;
                stack.push(nodeInSequence);

                while (!stack.isEmpty()) {
                    int node = stack.pop();

                    while (hasNonVisitedNeighbour(node)) {
                        stack.push(node);
                        node = nextNonVisitedNeighbour(node);
                        visited[node] = true;
                    }
                    output.push(node);
                }
            }
        }

        System.out.println("Topological Sort");
        System.out.println("-----------------");
        while (!output.isEmpty()) {
            System.out.println(output.pop());
        }
    }
}

- Nandhan Thiravia

Answer 8

以下是我用迭代方式编写的有向无环图拓扑排序代码。

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <stack>
using namespace std;

unordered_map<int, unordered_set<int>> g;  // this is the simplest graph representation I was able to implement. Map the vertices to their set of children

void addEdge(int x, int y) { // Add edges to the graph
    g[x].insert(y);
}

void topSort() {
    unordered_set<int> visited; // Keep track of visited nodes
    stack<int> mainStack; // The stack that will have the resulting vertices in topologically sorted order

    for(auto it = g.begin(); it != g.end(); it++) {
        if(visited.count(it->first) == 0) { // If the vertex was not already visited do the following
            visited.insert(it->first); // visit the vertex
            stack<int> locStack;
            locStack.push(it->first); // push it to local stack
            while(!locStack.empty()) { // This part is similar to basic DFS algorithm
                int curr = locStack.top();
                bool unVisCh = false; // Keep a boolean to check whether there is any unvisited child
                for(auto it2 = g[curr].begin(); it2 != g[curr].end(); it2++) {
                    int child = *it2;
                    if(visited.count(child) == 0) {
                        unVisCh = true;
                        visited.insert(child);
                        locStack.push(child);
                    }
                }
                if(!unVisCh) { // if there is no unvisited child then we can push the vertex to the resulting stack
                    locStack.pop();
                    mainStack.push(curr);
                }
            }
        }
    }

    while(!mainStack.empty()) {
        cout<<mainStack.top()<<" ";
        mainStack.pop(); // print them in order
    }
    cout<<endl;
}

int main() {
    addEdge(1,2);
    addEdge(4,5);
    addEdge(5,6);
    addEdge(3,2);
    addEdge(2,6);
    addEdge(1,3);
    addEdge(4,3); // add adges to the graph

    topSort();

    return 0;
}

测试用：ideone

- erol yeniaras

---

您的算法有误，其正确性取决于无序邻接信息的处理顺序。问题在于它不会将重复元素添加到堆栈中 - 如果一个节点已被添加到堆栈中（并标记为已访问），则算法无法从不同路径穿过相同的节点，错误地认为这个无法穿越节点的祖先是在后序访问，并添加到您的 mainStack。错误证明：http://cpp.sh/2onzk - plasmacel

Answer 9

又来了。:-) 我提交了一个答案，因为我没有足够的点来进行评论。:(

好吧，让我说我非常喜欢这个算法。如果图以正确的方式定义，那么就不会出错。但是看看这张图：

vector<vector<int>> graph
{
     { 2, 1 }
    ,{ 2 }
    ,{ }
};

这将显示： 2 1 2 0

为了保护自己免受以这种方式定义的图表或边缘随机的影响，您可以执行以下操作：

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    stack<pair<bool, int>> dfs;
    stack<int> postorder;
    vector<int> newvector;
    vector<int>::iterator it;
    vector<vector<int>> graph
    {
         { 2, 1 }
        ,{ 2 }
        ,{ }
    };

    vector<bool> visited(graph.size());
    vector<bool> finallyvisited(graph.size());

    for (int i = 0;i < graph.size();i++)
    {
        if (!visited[i])
        {
            dfs.push(make_pair(false, i));
        }

        while (!dfs.empty())
        {
            pair<bool, int> node = dfs.top();
            dfs.pop();
            if (node.first)
            {
                if (!finallyvisited[node.second])
                {
                    finallyvisited[node.second] = true;
                    postorder.push(node.second);
                    cout << node.second << endl;
                }
                continue;
            }

            visited[node.second] = true;
            dfs.push(make_pair(true, node.second));
            newvector = graph[node.second];
            for (it = newvector.begin();it != newvector.end();it++)
            {
                int son = *it;
                if (!visited[son])
                {
                    dfs.push(make_pair(false, son));
                }
            }
        }
    }
    return 0;
}

或者你可以预订图表，也许有人可以展示那个解决方案。如何预先随机给定边缘，以免需要进行第二次检查。:-)

我确实考虑了Atif Hussain的评论，但是那是错误的。那永远不会起作用。您总是希望尽可能晚地将节点推入堆栈，以便尽可能早地弹出。

- Laszlo

---

虽然我们欣赏您希望帮助他人的愿望，但这不是正确的方法。首先，“我无法评论，所以我提交了一个答案”不被接受 - 不要将评论发布为答案。你帖子的主要部分是一个真正的答案，那很好；但你最后关于Atif Hussain答案的几行话根本不属于这里。特别是如果你没有什么确切的话要说（毕竟，你所说的是“我不知道”）。 话虽如此... 这个问题标记为C++，为什么你要发布一个C#解决方案呢？如果你想提出你的解决方案，请坚持使用C++。我的建议是删除这篇文章。抱歉！ - Fabio says Reinstate Monica

你对这个旧问题的晚回答可能是毫无用处的，因为已经有一个被接受的答案（日期为2013年11月）。而且你的回答甚至是错误的编程语言，因为这个问题标记了 [tag:c++]。 - J.J. Hakala