Comment puis-je vérifier si un graphe orienté est acyclique?

Question

Comment puis-je vérifier si un graphe orienté est acyclique? Et comment est l'algorithme appelé? J'aimerais avoir une référence.

Answer 1

Je voudrais essayer de trier le graphe topologique, et si vous ne pouvez pas, alors elle a des cycles.

Answer 2

Faisant un simple de la profondeur de la première recherche n'est pas assez bon pour trouver un cycle. Il est possible de visiter un nœud à plusieurs reprises dans un DFS sans un cycle existant. Selon l'endroit où vous commencez, vous pourriez aussi ne pas visiter l'ensemble du graphique.

Vous pouvez vérifier les cycles dans une composante connexe d'un graphe comme suit. Trouver un nœud qui n'a qu'sortant bords. S'il n'existe pas de nœud, alors il existe un cycle. Démarrer un DFS au niveau de ce nœud. Lors de la traversée de chaque bord, vérifier si le bord de points sur un nœud déjà sur votre tapis. Cela indique l'existence d'un cycle. Si vous ne trouvez pas de tels bord, il n'existe pas de cycles dans ce composant connecté.

Comme Rutger Prins, si votre graphique n'est pas connecté, vous avez besoin de répéter la recherche sur chaque composante connexe.

Comme une référence, Tarjan est fortement composante connexe de l'algorithme est étroitement liée. Il sera également vous aider à trouver les cycles, et pas seulement le rapport qu'ils existent.

Answer 3

Lemme 22.11 sur le Livre Introduction aux Algorithmes (Deuxième Édition) stipule que:

"Un graphe orienté G est acyclique si et seulement si la profondeur d'abord la recherche de G ne donne aucun retour bords"

Answer 4

Je sais que c'est un vieux sujet, mais pour les futurs chercheurs ici C# de mise en œuvre que j'ai créé (pas de prétendre que c'est plus efficace!). Il est conçu pour utiliser un simple entier pour identifier chaque nœud. Vous pouvez décorez comme vous le souhaitez à condition que votre nœud objet hachages et est égal correctement.

Pour les Très profonde graphiques que cela peut avoir, haut dans le ciel, car elle crée un hashset à chaque nœud de profondeur (ils sont détruits au cours de l'ampleur).

Vous entrez le nœud à partir duquel vous voulez la recherche et le chemin à prendre pour ce nœud.

• Pour un graphe avec un seul nœud racine vous envoyer ce nœud et d'un vide hashset
• Pour un graphe ayant de multiples nœuds racine vous envelopper ce dans un foreach sur ces nœuds et de passer un nouveau vide hashset pour chaque itération

• Lors de la vérification des cycles ci-dessous un nœud donné, il suffit de passer le nœud le long avec un vide hashset

  private bool FindCycle(int node, HashSet<int> path)
  {
  
      if (path.Contains(node))
          return true;
  
      var extendedPath = new HashSet<int>(path) {node};
  
      foreach (var child in GetChildren(node))
      {
          if (FindCycle(child, extendedPath))
              return true;
      }
  
      return false;
  }