三维图可达顶点算法性能优化方案咨询

我已实现一款带记忆化的三维图自定义可达顶点算法及代码，但性能不足，希望找到可行的提速方案。

考虑如下问题：设图G包含V个节点和E条随机有向边，图足够稠密（E -> V^2）且含环。K是V的子集，需为K中每个顶点计算可达顶点集合。

图G中每个顶点v_i有S种状态（i = {1...S}），每种状态有独立的可达顶点缓存，因此可将该图视为三维图。

当前算法基于迭代DFS实现，搭配缓存系统，该系统为图中每个顶点状态维护一个缓存，存储对应状态下该顶点的可达顶点集合。

经性能分析，约80%的耗时用于排序，导致算法在含环且E->V^2的图上性能极差。当前实现中，每次结束顶点访问时执行以下操作：

1. 获取该顶点缓存中的可达顶点，进行排序与压缩，合并不同状态的重复顶点；
2. 将当前访问的顶点添加至父顶点的可达顶点缓存；
3. 将当前顶点缓存中的可达顶点添加至父顶点的缓存。

procedure EndVisit(X):
  reachable_vertices = cache_get(X)->reachable_vertices_get // N elements
  sortAndCompact(reachable_vertices)                        // K elements | K <= N

  // parent from the current DFS stack:
  parent_reachable_vertices = parent_cache_get(X)->reachable_vertices_get 
  parent_reachable_vertices.append(X)
  parent_reachable_vertices.append(reachable_vertices)

考虑一个含环的简单图：
示例图：包含顶点A、B、C、D的有向含环图，顶点间存在多条有向边且形成环结构。

需计算顶点B（状态1）和顶点A（状态1）的可达顶点集合，以下是修改后的迭代DFS执行过程（DFS路径随机）：

call ReachableVerticesGet(vertex: B, state: 1):
  - [b1]
  - [b1,c1]
  Call EndVisit ==> c1 {}, b1 {c1}
  - [b1]
  - [b1,a1]
  - [b1,a1,b2]
  - [b1,a1,b2,c1]
  Call EndVisit ==> c1 {}, b2 {c1}
  - [b1,a1,b2]
  - [b1,a1,b2,a1] Cycle detected, we mark it
  Call EndVisit ==> a1 {}, b2 {c1,a1}
  - [b1,a1,b2]
  Call EndVisit ==> b2 {c1,a1}, a1 {b2,c1,a1}
  - [b1,a1]
  - [b1,a1,d1]
  - [b1,a1,d1,b2]
  - [b1,a1,d1,b2,c1]
  Call EndVisit ==> c1 {}, b2 {c1,a1,c1}
  - [b1,a1,d1,b2] 
  - [b1,a1,d1,b2,a1] Cycle detected, we mark it
  Call EndVisit ==> a1 {b2,c1,a1}, b2 {c1,a1,c1,a1,b2,c1,a1}
  - [b1,a1,d1,b2]
  Call EndVisit ==> b2 {b2,c1,a1}, d1 {b2,b2,c1,a1}
  - [b1,a1,d1]
  Call EndVisit ==> d1 {b2,c1,a1}, a1 {b2,c1,a1,d1,b2,c1,a1}
  - [b1,a1]
  Call EndVisit ==> a1 {b2,c1,a1,d1}, b1 {c1,a1,b2,c1,a1,d1}
  - [b1]
  Call EndVisit ==> b1 {c1,a1,b2,d1}
  return {c1,a1,b2,d1}
 
call ReachableVerticesGet(vertex: A, state: 1):
  A's cache contains {b2,c1,a1,d1}
  return {b2,c1,a1,d1}

该算法可正常工作，通过了含环图、随机图等大量测试，仅少数退化案例耗时异常，但整体正确性有保障。核心问题是性能极差：

1. 若移除EndVisit()中的SortAndCompact()，内存会迅速飙升至32GB以上（无内存泄漏）；
2. 每次结束顶点访问都调用std::sort，在含环、多状态图中，同一顶点可能被多次排序。虽std::sort在当时是合理选择，但需更优方案。

• 用set/unordered_set替代vector存储可达顶点缓存，测试后性能无明显提升，耗时从std::sort转移至std::set::insert；
• 尝试通过克隆缓存并行化算法，但缓存合并难度极大，已放弃；
• 用std::pmr（多态资源类型）在栈上创建unordered_map替代std::sort去重，性能提升约25%，但仍未达标；
• 仅缓存算法起始顶点的可达结果，而非动态缓存所有中间顶点，导致部分场景下50万+缓存命中失效，性能下降；
• 考虑内存阈值触发SortAndCompact()的轮询机制，性能反而下降，已放弃；
• 针对强连通分量图，尝试预设置DFS顶点优先级，无量化提升；
• 考虑重写算法，但耗时过长，优先寻求现有优化方案。

我围绕减少、消除、加速std::sort调用尝试了多种技巧，但仍无头绪，希望在替换算法前获取专业建议。

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