Est-ce le meilleur algorithme pour détecter un cycle dans un graphe non orienté?

Question

L'algorithme C# suivant que j'ai écrit détecte l'existence d'un cycle dans un graphique non orienté en temps O (n). Il évite la récursion et profite du hachage via les Dictionnaires et les HashSets. Mais y a-t-il un moyen de faire mieux?

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 est la meilleure façon de déterminer les cycles dans un graphe

Geeksforgeeks cycle detect from undirected graph

Je vous renvoie à l'étude d'ici et d'appliquer DSF.