DFS算法处理大型图性能过慢的优化方案咨询

问题背景 #

我在C#中实现了一个强连通图结构，示例如下：
原始边关系：

1,2
2,3
3,1

展开所有直接/间接成员关系后得到：

1,2
2,3
3,1
1,1
2,1
3,3
2,2
1,3
3,2

其中像1,1这类是间接成员关系（如1=>2=>3=>1）。

图的顶点存储在HashSet<long>中，强连通边用Dictionary<long, HashSet<long>>类型的adjList表示：

1, [2]
2, [3]
3, [1]

当前遍历所有路径的代码：

Dictionary<long, List<string>> flows = new Dictionary<long, List<string>>();
foreach (long s in verts)
{
    graph.printAllPaths(s);
}
flows = graph.flow;

图类的核心实现：

public Dictionary<long, List<string>> flow = new Dictionary<long, List<string>>();
public Dictionary<long, List<string>> printAllPaths(long s)
{
    HashSet<long> isVisited = new HashSet<long>();
    List<long> pathList = new List<long>();

    // add source to path[]
    pathList.Add(s);
    // Call recursive utility
    PrintAllPathsUtil(s, isVisited, pathList);
    return flow;
}

private void PrintAllPathsUtil(long u, HashSet<long> isVisited, List<long> localPathList)
{
    isVisited.Add(u);
    if (adjList.ContainsKey(u))
    {
        foreach (long v in adjList[u])
        {
            if (!isVisited.Contains(v) && !localPathList.Contains(v))
            {
                localPathList.Add(v);

                long first = localPathList[0];
                long last = localPathList[localPathList.Count - 1];
                string currentFlow = string.Join(">", localPathList);
                if (currentFlow.Contains(">"))
                {
                    if (NestedFlowMain.unqMemId.TryGetKey(NestedFlowMain.CantorPair(first, last), out long key))
                    {
                        if (flow.ContainsKey(key))
                        {
                            flow[key].Add(currentFlow);
                        }
                        else
                        {
                            flow.Add(key, new List<string> { currentFlow });
                        }
                    }
                }
                //get cyclic elements as well
                if (adjList.ContainsKey(last))
                {
                    if (adjList[last].Contains(first))
                    {
                        localPathList.Add(first);
                        string currentCycleFlow = string.Join(">", localPathList);
                        if (NestedFlowMain.unqMemId.TryGetKey(NestedFlowMain.CantorPair(first, first), out long cycleKey))
                        {
                            if (flow.ContainsKey(cycleKey))
                            {
                                flow[cycleKey].Add(currentCycleFlow);
                            }
                            else
                            {
                                flow.Add(cycleKey, new List<string> { currentCycleFlow });
                            }
                            localPathList.Remove(localPathList[localPathList.Count - 1]);
                        }
                    }
                }

                PrintAllPathsUtil(v, isVisited, localPathList);

                localPathList.Remove(v);
            }
        }
    }

    isVisited.Remove(u);
}

当前问题：处理小图速度正常，但面对500K顶点的大型图时性能极差，原因是递归遍历产生大量分支，求优化思路，尤其是备忘录模式的实现方法。

优化方案 #

1. 替换递归为迭代，避免栈开销与溢出 #

递归在处理深度大的图时会产生大量栈帧开销，甚至触发栈溢出。改用迭代式深度优先搜索（DFS），用栈模拟递归过程，手动管理访问状态和路径：

• 栈中存储元组：当前节点、临时访问标记集合、当前路径列表
• 优化点：避免每次复制HashSet，可采用标记位复用（比如用字典记录节点是否在当前路径中，离开时重置），或如果顶点ID连续，用BitArray替代HashSet，大幅降低内存开销

2. 预计算强连通分量（SCC），缩小处理范围 #

强连通图中，每个SCC内的节点互相可达，跨SCC的路径是单向的（针对有向图）。先用Tarjan算法或Kosaraju算法找出所有SCC：

• 对每个SCC单独处理内部的循环路径，避免重复遍历跨分量的无效路径
• 缓存每个SCC内节点的可达关系，比如记录(起点, 终点)对应的路径模板，复用已计算结果

3. 备忘录（缓存）优化，避免重复计算 #

核心是缓存已经计算过的(起点, 当前节点)对应的路径集合，避免重复遍历相同路径：

• 定义缓存字典：Dictionary<(long start, long current), List<List<long>>> _pathCache，键为起点+当前节点，值为从起点到当前节点的所有路径列表
• 遍历前先检查缓存：如果_pathCache中存在对应键，直接复用路径，无需重新遍历
• 注意：缓存存储原始路径列表（List<long>），而非字符串，减少序列化/反序列化开销，仅在需要存入flow时再转换为字符串

4. 数据结构优化，降低查找时间 #

当前代码多处存在*O(n)*的低效查找，替换为高效结构：

• 将localPathList.Contains(v)的O(n)检查，替换为并行维护的HashSet<long> _currentPathNodes，使查找操作降为O(1)
• 预处理adjList，确保所有顶点都有对应条目（即使是空HashSet），避免每次循环都执行adjList.ContainsKey(u)检查
• 预存CantorPair的键值映射到Dictionary<(long, long), long>，避免每次调用TryGetKey的开销

5. 延迟生成路径字符串，减少内存与CPU开销 #

当前每次添加节点都调用string.Join(">", localPathList)，这是高开销操作：

• 仅在需要存入flow时才生成字符串，或先存储路径的List<long>，最后统一批量转换
• 对于循环路径，无需临时添加起点再生成字符串，直接基于当前路径拼接$"{currentPathStr}>{first}"即可

备忘录模式具体实现示例 #

// 类内缓存：键为(起点, 当前节点)，值为该起点到当前节点的所有路径
private Dictionary<(long start, long node), List<List<long>>> _pathCache = new Dictionary<(long, long), List<List<long>>>();

private List<List<long>> GetAllPathsFromStart(long start, long currentNode)
{
    var cacheKey = (start, currentNode);
    if (_pathCache.TryGetValue(cacheKey, out var cachedPaths))
    {
        // 返回缓存的路径副本，避免原列表被修改
        return cachedPaths.Select(p => new List<long>(p)).ToList();
    }

    var paths = new List<List<long>>();
    // 起点到自身的基础路径
    if (start == currentNode)
    {
        paths.Add(new List<long> { start });
    }

    // 遍历当前节点的邻接节点
    if (adjList.TryGetValue(currentNode, out var neighbors))
    {
        foreach (var neighbor in neighbors)
        {
            // 获取从起点到邻接节点的所有路径
            var subPaths = GetAllPathsFromStart(start, neighbor);
            foreach (var subPath in subPaths)
            {
                // 避免路径中出现重复节点（根据需求调整，允许循环则去掉此判断）
                if (!subPath.Contains(currentNode))
                {
                    var newPath = new List<long> { currentNode };
                    newPath.AddRange(subPath);
                    paths.Add(newPath);
                }
            }
        }
    }

    // 缓存路径的副本，避免后续修改影响缓存
    _pathCache[cacheKey] = paths.Select(p => new List<long>(p)).ToList();
    return paths;
}

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