我们可以实施“白色，灰色，黑色”带有堆栈的DF而不是使用递归调用

Question

我正在尝试使用堆栈实现“白色灰色黑色DFS”。

白色黑色的概念下面是：

1. 如果尚未访问节点，则为white。
2. 如果只是将一个节点推入堆栈中，但尚未处理其邻居。 （DFS堆栈不是空的，DFS进程尚未遍及分支孩子），节点被标记为灰色。
3. 如果处理一个节点及其所有子节点，则标记为black。

对于（3）：

• 如果DFS到达分支的末端，节点没有任何子节点，则标记节点black
• 带有递归返回，所有父母节点都可以“回溯”并更改从灰色到黑色

现在我想实现同一件事，但是我不使用递归调用，而是使用堆栈来实现DFS遍历。出现一个问题：我无法回溯到父节点以将其标记为black

示例问题在此leetcode链接上： https://leetcode.com/problems/find-eventual-safe-states/

到目前为止，我目前的尝试：

class Solution {
    private:
        vector<int> visited;   
        // mark nodes as Not Visited=0; "In DFS Progress" = 1; at terminal, all processed and connected to terminal = 2
        // if revisiting In Progress node => a back-edge is found.
        bool dfs(vector<vector<int>>& graph, int node, vector<int>& result){
            stack<int> dfsStack;           
            dfsStack.push(node);
            while (!dfsStack.empty()){
                int currNode = dfsStack.top();
                dfsStack.pop();
                // if currNode connect to a node in In Progress
                if (currNode == 1){
                    return false;
                }   
                // mark gray, black for nodes in DFS progress, terminal nodes;
                if (graph[currNode].size()==0){              // mark terminal node as 2
                    visited[currNode] = 2;
                    // set all parents node as 2 ===>>>> HOW TO DO THIS???? 
                }
                else 
                    visited[currNode] = 1;                    // mark node in progress as 1
                // process neighbor:
                for (int i = 0; i < graph[currNode].size(); i++){
                    int nextNode = graph[currNode][i];
                    dfsStack.push(nextNode);
                }
            }
            return true; 
        }
    public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> result;
        visited.resize((graph.size(),0));                   // all nodes are not yet visited
        for (int node=0; node<graph.size(); node++){
            if (dfs(graph, node, result)
                result.push_back(node);
        }
        return result; 
    }
};

我正在学习，并加深我的理解，并加深我的理解，我有一种用几种方法实施每件事的习惯。

Answer 1

当您递归实现DFS时，递归调用来处理孩子使用呼叫堆栈来记住父节点和父母列表中的当前位置。

当孩子完成后，对父母节点的处理处理将继续，其中包括检测何时没有孩子和父母的任何最终处理，例如“标记黑色”。

您的迭代实现无法正常工作。当您开始处理父母时，您将全部将其孩子推向堆栈，而忘记了父母。堆栈不像递归版本中那样包含进展中的节点。它包含您尚未访问的节点。这意味着您不记得执行任何最终父母处理所需的信息。

您需要通过更改记住的内容来使迭代实现更像递归的实现。有许多不同的方式。例如，您可以像递归版本一样，记住一个节点堆栈和位置堆栈，而是可以记住当前的父母和位置。由于您使用相同类型的节点和位置，因此您甚至可以在同一堆栈上交替使用它们。

但是请注意：您似乎正在使用DFS进行周期检测。由于我们在这里谈论的是额外的并发症，因此我通常使用 a>为此。