cycle - 这是在无向图中检测循环的最佳算法吗？

Question

我编写的以下 C# 算法在 O(n) 时间内检测到无向图中是否存在循环。它避免了递归，并通过字典和哈希集利用散列。但是有没有办法让我做得更好？

void Main()
{
    var graph = new Dictionary<int, HashSet<int>>
    {
        { 0, new HashSet<int> { 4 } },
        { 1, new HashSet<int> { 2, 3, 4 } },
        { 2, new HashSet<int> { 1 } },
        { 3, new HashSet<int> { 1, 4 } },
        { 4, new HashSet<int> { 0, 1, 3 } }
    };

    Console.WriteLine(HasCycle(graph, 0));
}

bool HasCycle(Dictionary<int, HashSet<int>> graph, int start)
{
    var stack = new Stack<int>();
    var visited = new HashSet<int>();
    stack.Push(start);
    var curr = start;
    var prev = -1;
    while (stack.Count > 0)
    {
        prev = curr;
        curr = stack.Pop();
        visited.Add(curr);
        HashSet<int> neighbors;
        if (graph.TryGetValue(curr, out neighbors) && neighbors != null)
        {
            foreach (var neighbor in neighbors)
            {
                if (!visited.Contains(neighbor))
                {
                    stack.Push(neighbor);
                }
                else if (neighbor != prev && neighbors.Contains(prev))
                {
                    return true;
                }
            }
        }
    }
    return false;
}

Answer 1

DFS 是确定图中循环的最佳方法

Geeksforgeeks 循环检测无向图

我会推荐你​​从这里学习并申请 dfs。