我们能否使用堆栈实现"White, Gray, Black" DFS而不是使用递归调用

Question

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

White Gray Black的概念如下:

1. 如果节点尚未访问，则为White。
2. 如果一个节点刚刚被推入堆栈，但它的邻居还没有被处理。(DFS堆栈不是空的，DFS进程还没有遍历到分支子节点)，节点被标记为Gray。
3. 如果一个节点及其所有子节点被处理，则标记为Black。

(3):

• 如果DFS到达分支的末端，该节点没有任何子节点，则标记为Black
• 使用递归返回，所有父节点都可以"回溯"。并由Gray改为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进行周期检测。由于我们在这里讨论的额外复杂性，我通常使用Kahn的算法。