これは、無向グラフのサイクルを検出するための最良のアルゴリズムですか？

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は、私がここから勉強し、DFSを適用するためにあなたを参照することになり、グラフに

Geeksforgeeks cycle detect from undirected graph

サイクルを決定するための最良の方法です。