如何使用栈替代递归实现白灰黑三色DFS及节点回溯标记

原有实现无法完成回溯标记的核心原因是：栈中仅存储了节点编号，无法区分「节点首次访问，待遍历邻接节点」和「节点所有邻接节点处理完成，待回溯标记状态」两个阶段，自然无法触发父节点转Black的逻辑。

解决方法是给栈元素增加访问状态标记，用二元组(节点id, 是否已完成邻接节点处理)作为栈元素，完全模拟递归调用的栈帧生命周期：

• 当弹出的元素标记为「未完成邻接处理」时，对应递归函数刚进入节点的阶段：标记节点为Gray，再把当前节点以「已完成邻接处理」的状态重新压栈，之后压入所有邻接节点等待处理
• 当弹出的元素标记为「已完成邻接处理」时，对应递归函数处理完所有子节点准备返回的阶段：此时所有子节点的状态已经确定，直接判断当前节点是否所有邻接节点都是Black安全节点，是则标记当前节点为Black，否则标记为可达环的非安全节点

完整状态规则 #

• 0 = White：节点未访问
• 1 = Gray：节点在当前DFS路径中，处理中
• 2 = Black：节点及所有子节点处理完成，为安全节点

修正后可运行代码 #

class Solution {
private:
    vector<int> state;
    bool dfs(vector<vector<int>>& graph, int start) {
        stack<pair<int, bool>> stk;
        stk.push({start, false});
        while (!stk.empty()) {
            auto [curr, is_processed] = stk.top();
            stk.pop();
            // 回溯阶段：所有邻接节点处理完成，标记当前节点状态
            if (is_processed) {
                bool is_safe = true;
                for (int neighbor : graph[curr]) {
                    if (state[neighbor] != 2) {
                        is_safe = false;
                        break;
                    }
                }
                state[curr] = is_safe ? 2 : 1;
                continue;
            }
            // 首次访问节点的处理逻辑
            if (state[curr] == 1) return false; // 碰到处理中节点，存在环
            if (state[curr] == 2) continue; // 已经是确认过的安全节点，跳过
            // 先压入回溯阶段的标记，再压入邻接节点
            stk.push({curr, true});
            state[curr] = 1;
            // 倒序压入邻接节点保证遍历顺序和递归一致，不要求顺序可直接正序压
            for (auto it = graph[curr].rbegin(); it != graph[curr].rend(); ++it) {
                int neighbor = *it;
                if (state[neighbor] == 1) return false; // 邻接节点在处理中，直接判定有环
                if (state[neighbor] == 0) stk.push({neighbor, false});
            }
        }
        return state[start] == 2;
    }
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        state.resize(n, 0);
        vector<int> res;
        for (int i = 0; i < n; ++i) {
            if (state[i] == 2 || dfs(graph, i)) {
                res.push_back(i);
            }
        }
        return res;
    }
};

注意点 #

• 原有代码存在一个语法bug：visited.resize((graph.size(),0))多嵌套了一层括号，会被解析为逗号表达式，实际初始化的数组长度为0，运行时会出现内存越界。
• 该实现时间复杂度为O(N+E)，和递归版本完全一致，每个节点、每条边仅会被处理一次。
• 栈中每个节点最多被压入两次（首次访问、回溯标记），空间复杂度为O(N)。

内容的提问来源于stack exchange，提问作者Minh Pham