3. 基于深度优先的拓扑排序：依赖关系处理、循环检测与修复

3.1 原理概述

深度优先搜索（DFS）天然适合对有向图进行拓扑排序，并能同时完成循环检测。核心思路是沿着依赖链递归深入，直到某个节点不再有未处理的依赖项，然后将其记录到最终顺序中。如果递归过程中遇到正在处理中的节点（即递归栈回溯路径上的节点），则判定存在循环依赖。

3.2 实现流程

1. 图表示： 使用邻接表（unordered_map<int, vector<int>>）存储节点 ID 到其依赖项列表的映射。
2. 初始化： 为所有节点创建 UNVISITED 状态。
3. 遍历： 对每个 UNVISITED 的节点启动 DFS。
4. 检测： 进入节点时标记为 VISITING，遇到 VISITING 邻居则停止并报告循环。
5. 回溯： 递归完成后将节点标记为 VISITED 并压入排序栈。
6. 输出： 逆序弹出栈，得到拓扑排序结果。

3.3 核心代码实现（C++）

#include <unordered_map>
#include <vector>
#include <stack>

enum class NodeStatus { UNVISITED, VISITING, VISITED };

class TopologicalSorter {
public:
    bool sort(const std::unordered_map<int, std::vector<int>>& graph,
              std::vector<int>& result) {
        std::unordered_map<int, NodeStatus> status;
        std::stack<int> order;
        bool hasCycle = false;

        for (const auto& pair : graph) {
            if (status[pair.first] == NodeStatus::UNVISITED) {
                if (dfs(graph, pair.first, status, order, hasCycle)) {
                    return false; // 存在循环，终止
                }
            }
        }

        while (!order.empty()) {
            result.push_back(order.top());
            order.pop();
        }
        return true;
    }

private:
    bool dfs(const std::unordered_map<int, std::vector<int>>& graph,
             int node,
             std::unordered_map<int, NodeStatus>& status,
             std::stack<int>& order,
             bool& hasCycle) {
        if (status[node] == NodeStatus::VISITING) {
            hasCycle = true;
            return true;
        }
        if (status[node] == NodeStatus::VISITED) {
            return false;
        }

        status[node] = NodeStatus::VISITING;

        auto it = graph.find(node);
        if (it != graph.end()) {
            for (int neighbor : it->second) {
                if (dfs(graph, neighbor, status, order, hasCycle)) {
                    return true;
                }
            }
        }

        status[node] = NodeStatus::VISITED;
        order.push(node);
        return false;
    }
};

3.4 调试与日志记录

为便于追踪依赖解析过程，建议输出详细的遍历日志：

[DEBUG] 开始处理节点 5（区域：Boss 房间）
[DEBUG] 节点 5 依赖于节点 3（钥匙房间）
[DEBUG] 节点 3 状态：UNVISITED，开始递归
[DEBUG] 节点 3 无依赖项，标记为 VISITED
[DEBUG] 节点 5 所有依赖已处理，标记为 VISITED
[WARN] 检测到循环依赖：节点 7 -> 节点 9 -> 节点 7
[ERROR] 拓扑排序失败，无法生成加载序列

3.5 部署与集成

将拓扑排序封装为独立模块，通过统一接口接入场景加载系统：

• 输入： 场景地图的 JSON 配置或运行时图结构。
• 输出： 排序后的节点 ID 向量，或包含循环路径的错误信息。

// 集成示例
TopologicalSorter sorter;
std::vector<int> loadOrder;
if (sorter.sort(sceneGraph, loadOrder)) {
    SceneLoader::LoadScenesByOrder(loadOrder);
} else {
    ErrorHandler::ReportCycle(sorter.GetCycleTrace());
    // 触发默认加载策略或直接终止
}

3.6 常见错误与修复

3.7 性能与稳定性优化

• 空间优化： 若节点 ID 为连续整数，使用 std::vector<NodeStatus> 或 std::bitset<N> 替代哈希表，可减少内存占用并提升缓存命中率。
• 时间优化： 缓存拓扑排序结果；仅在场景地图的结构（节点或依赖关系）发生变更时触发重新计算。
• 稳定性： 设置递归深度阈值（如 1024 层），超时则判定为数据异常并主动终止遍历，防止由于配置损坏导致死循环。