大图的DFS算法太慢

Question

我在 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 相关（1 => 2 => 3 => 1）等等。（此信息稍后会有意义）

图的顶点是 [1, 2, 3] 并存储在

HashSet<long>

我有一个名为 adjList 的边字典，它存储强连接的边，在

Dictionary<long, HashSet<long>>

中，这样：

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;

graph类中调用的方法如下：

    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 的顶点，代码就会非常慢。我理解这是因为每个顶点可以有多个它们要去的节点，并且每个节点还可以有多个它们要去的节点，依此类推。

有没有办法提高效率？我读到了有关记忆的内容，但不确定在这种情况下如何实现它。希望有任何见解。

谢谢你。

Answer 1

我无法确切地说出为什么你的代码很慢。要找出这一点，您应该运行一些分析工具来准确检查时间花在哪里。我的猜测是，您的代码中存在一些缓慢的操作，例如字符串操作或有关“流程”的操作，这些操作占用了大部分时间。我不明白代码实际上应该做什么，所以我无法真正判断您是否在做不必要的工作。

我还会关注对大图使用递归，尤其是 DFS。这可能会耗尽堆栈，因此您可能需要使用带有显式堆栈的迭代。

但是你应该能够相当快地做某事。以通用迭代器为例：

public static IEnumerable<T> DepthFirstLoopSafe<T>(T self, Func<T, IEnumerable<T>> selector, Maybe<IEqualityComparer<T>> equalityComparer = default)
{
    var stack = new Stack<T>();
    var visited = new HashSet<T>(equalityComparer.Else(EqualityComparer<T>.Default));
    stack.Push(self);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        if(!visited.Add(current)) continue;
        yield return current;
        foreach (var child in selector(current))
        {
            if (!visited.Contains(child))
            {
                stack.Push(child);
            }
        }
    }
}

以及一些生成测试图表的代码：

var edgeList = new Dictionary<int, List<int>>();
var rand = new Random();
int nodeCount = 500000;
var edgesperNode = 100;
for (int i = 0; i < nodeCount; i++)
{
    var list =new List<int>();
    for (int j = 0; j < edgesperNode; j++)
    {
        list.Add(rand.Next(0, nodeCount));
    }

    edgeList[i] = list;
}

var sw = Stopwatch.StartNew();
var nodes = Tree.DepthFirstLoopSafe(0, node => edgeList[node]).ToList();
sw.Stop();
Console.WriteLine($"Time: {sw.ElapsedMilliseconds}ms, found nodes {nodes.Count}");

这需要我运行大约 1500 毫秒，这可能是我在使用边缘字典时所期望的。我知道这比你的代码做的事情少，但我无法确切地告诉你在做什么，所以我无法复制它。但我希望这至少应该表明问题不一定是遍历，而是限制性能的处理。

如果您需要更多数据，例如父级或当前深度，则将其添加到迭代器应该相当简单。只需更改堆栈参数并将值返回到元组，并相应地调整其余代码即可。我预计这对性能的影响相当小。