這是在無向圖中檢測週期的最佳算法嗎？

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 cycle detect from undirected graph

我要提到你在這裏學習和運用DFS循環的最佳方式。