이것은 방향이없는 그래프의주기를 감지하는 가장 좋은 알고리즘입니까?

Question

내가 작성한 다음 C# 알고리즘은 O (n) 시간에 무향 그래프의주기 존재를 감지합니다. 그것은 재귀를 피하고 사전과 HashSet을 통한 해시를 이용합니다. 그러나 내가 더 잘할 수있는 방법이 있습니까?

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를 적용 할을 참조 할에 사이클을 결정하는 가장 좋은 방법입니다.