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

Question

Comment puis-je vérifier si un graphe orienté acyclique est? Et comment est l'algorithme appelé? Je vous serais reconnaissant une référence.

Answer 1

Je voudrais essayer de trier le graphique topologiquement , et si vous ne pouvez pas, alors il a des cycles.

Answer 2

Faire une profondeur de première recherche 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 aussi pourriez ne pas visiter l'ensemble du graphique.

Vous pouvez vérifier les cycles dans un composant connecté d'un graphe comme suit. Trouver un noeud qui a des bords que sortants. S'il n'y a pas de tel noeud, alors il y a un cycle. Démarrez un DFS à ce nœud. En traversant chaque bord, vérifier si le bord pointe vers un nœud déjà sur votre pile. Cela indique l'existence d'un cycle. Si vous ne trouvez pas ce bord, il n'y a pas de cycles dans ce composant connecté.

Rutger Prins souligne, si votre graphique est pas connecté, vous devez répéter la recherche sur chaque composant connecté.

En tant que référence, algorithme de composante fortement connexe de Tarjan est étroitement liée . Il vous aidera également à trouver les cycles, non seulement d'indiquer si elles existent.

Answer 3

Lemme 22.11 sur le Introduction to Algorithms livre (deuxième édition) stipule que:

  

Un graphe orienté G est acyclique si et seulement si une recherche en profondeur d'abord de G cède pas des bords arrière

Answer 4

Solution1 : algorithme Kahn pour vérifier le cycle . Idée principale: Maintenir une file d'attente où le nœud avec zéro degré sera ajouté dans la file d'attente. Retirer ensuite noeud un par un jusqu'à ce que la file d'attente est vide. Vérifiez si-bords de tout nœud sont existaient.

Solution2 . algorithme Tarjan pour vérifier la composante connexe forte

solution3 : DFS . Utiliser réseau entier pour marquer état actuel du noeud: à savoir 0 --means ce noeud n'a pas été visité.      -1 - signifie que ce noeud a été visité, et ses enfants noeuds sont visités.      1 - signifie que ce noeud a été visité, et il est fait. Donc, si l'état d'un nœud est -1 tout en faisant DFS, cela signifie qu'il doit y avoir un cycle existait.

Answer 5

La solution donnée par ShuggyCoUk est incomplète, car il pourrait ne pas vérifier tous les nœuds.

def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

a timecomplexity O (n + m) ou O (n ^ 2)

Answer 6

Je sais que c'est un vieux sujet, mais pour les chercheurs à venir ici est une implémentation C # j'ai créé (ne prétend pas que c'est le plus efficace!). Il est conçu pour utiliser un simple entier pour identifier chaque noeud. Vous pouvez décorer que comme bon vous semble à condition que votre objet nœud hash et égaux correctement.

Pour les graphiques très profonds cela peut avoir des frais généraux élevés, car il crée un HashSet à chaque noeud en profondeur (ils sont détruits sur la largeur).

Vous entrez le noeud à partir duquel vous souhaitez rechercher et le chemin à prendre ce nœud.

• Pour un graphique avec un seul nœud racine vous envoyer ce nœud et un HashSet vide
• Pour un graphique ayant plusieurs nœuds racine vous enveloppent cela dans un foreach sur ces noeuds et passer une nouvelle HashSet vide pour chaque itération

• Lors de la vérification des cycles ci-dessous tout noeud donné, il suffit de passer le long de ce noeud avec un HashSet vide

  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;
  }
  

Answer 7

Il ne devrait pas y avoir de bord arrière tout en faisant des nœuds piste DFS.Keep déjà visités tout en faisant DFS, si vous rencontrez un bord entre le noeud courant et nœud existant, puis graphique a cycle.

Answer 8

ici est un code rapide pour trouver si un graphe a des cycles:

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{

    if(breadCrumb[root] == true)
    {
        return true;
    }

    if(visited[root] == true)
    {
        return false;
    }

    visited[root] = true;

    breadCrumb[root] = true;

    if(G[root] != nil)
    {
        for child : Int in G[root]!
        {
            if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
            {
                return true;
            }
        }
    }

    breadCrumb[root] = false;
    return false;
}


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];

var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

L'idée est comme ceci: un algorithme de DSF normale avec un tableau pour garder une trace des noeuds visités, et un tableau supplémentaire qui sert de marqueur pour les noeuds qui ont conduit au noeud courant, de sorte que chaque fois que nous exécutons un DSF pour un nœud que nous fixons son élément correspondant dans le tableau de marqueur comme vrai, de sorte que si jamais un nœud déjà visité rencontré, nous vérifions si son élément correspondant dans le tableau de marqueur est vrai, si son vrai, alors l'un des noeuds qui permettent de se (Donc un cycle), et le tour est à chaque fois qu'un DSF d'un noeud ayant nous avons mis son marqueur correspondant à revenir faux, de sorte que si nous avons visité à nouveau d'une autre route que nous ne sommes pas dupes.

Answer 9

Voici ma mise en œuvre rubis de la peau au large feuille algorithme de noeud .

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end

Answer 10

Je viens juste de cette question dans une interview Google.

Trier topologiques

Vous pouvez essayer de sorte topologiquement, qui est O (V + E) où V est le nombre de sommets et E est le nombre d'arêtes. Un graphe orienté acyclique est si et seulement si cela peut se faire.

récursive feuilles Suppression

Le supprimer récursive nœuds feuilles jusqu'à ce qu'il n'y en a pas à gauche, et s'il n'y a plus qu'un seul nœud que vous avez laissé un cycle. À moins que je me trompe, c'est O (V ^ 2 + VE).

DFS de style ~ O (n + m)

Cependant, un algorithme efficace DFS-esque, le pire des cas O (V + E), est:

function isAcyclic (root) {
    const previous = new Set();

    function DFS (node) {
        previous.add(node);

        let isAcyclic = true;
        for (let child of children) {
            if (previous.has(node) || DFS(child)) {
                isAcyclic = false;
                break;
            }
        }

        previous.delete(node);

        return isAcyclic;
    }

    return DFS(root);
}