Come posso controllare se un grafo orientato è aciclico?

Question

Come posso controllare se un grafo orientato è aciclico? E come si chiama l'algoritmo? Gradirei un riferimento.

Answer 1

Vorrei provare a ordinare il grafico topologicamente , e se non è possibile, allora esso ha cicli.

Answer 2

Facendo una semplice in profondità-ricerca è non abbastanza buono per trovare un ciclo. E 'possibile visitare un nodo più volte in un DFS senza un ciclo esistente. A seconda di dove si inizia, anche voi non potreste visitare l'intero grafico.

È possibile verificare cicli in una componente connessa di un grafico come segue. Trova un nodo che ha i bordi solo uscenti. Se non v'è tale nodo, allora c'è un ciclo. Avviare un DFS in quel nodo. Quando attraversano ogni bordo, controllare se punta il bordo posteriore di un nodo già sul tuo stack. Ciò indica l'esistenza di un ciclo. Se si trova tale bordo, ci sono dei cicli in quella componente collegato.

Come Rutger Prins fa notare, se il grafico non è collegato, è necessario ripetere la ricerca su ogni componente collegato.

Come riferimento, algoritmo componente fortemente connessa di Tarjan è strettamente correlata . Essa aiuterà anche a trovare i cicli, non solo comunica se esistono.

Answer 3

Lemma 22.11 sul Introduction to Algorithms libro (Second Edition) afferma che:

  

Un grafo orientato G è aciclico se e solo se una ricerca in profondità di G cede senza bordi posteriori

Answer 4

Soluzione 1 : algoritmo di Kahn per controllare il ciclo . L'idea principale: mantenere una coda in cui nodo con zero gradi sarà aggiunto in coda. Quindi rimuovere nodo uno per uno fino coda è vuota. Controllare se sono esistiti in-bordi di ogni nodo.

Solution2 :. Tarjan algoritmo per verificare forte componente collegato

Solution3 : DFS . Utilizzare matrice integer per codificare lo stato attuale del nodo: cioè 0 --means questo nodo non è stato visitato prima.      -1 - significa che questo nodo è stato visitato, e le sue nodi bambini sono stati visitati.      1 - significa questo nodo è stato visitato, ed è fatta. Quindi, se lo stato di un nodo è -1, mentre facendo DFS, significa che ci deve essere esistito un ciclo.

Answer 5

La soluzione proposta dal ShuggyCoUk è incompleta perché potrebbe controllare tutti i nodi.

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

Questo ha timecomplexity O (n + m) o O (n ^ 2)

Answer 6

So che questo è un argomento vecchio, ma per i ricercatori futuri: ecco un implementazione C # che ho creato (senza pretesa che è più efficiente!). Questo è progettato per utilizzare un intero semplice per identificare ciascun nodo. Potete decorare che più vi piace a condizione che il hash oggetto nodo e uguale correttamente.

Per i grafici molto profonde questo può avere molto in alto, in quanto crea un hashset ad ogni nodo in profondità (sono distrutti sopra larghezza).

inserire il nodo da cui si desidera effettuare la ricerca e il percorso prendere per quel nodo.

• Per un grafico con un singolo nodo radice si invia tale nodo e un hashset vuoto
• Per un grafico avente più nodi radice si avvolgono questo in un foreach su tali nodi e passare un nuovo hashset vuota per ciascuna iterazione

• Durante la prova di cicli di sotto di qualsiasi dato nodo, basta passare quel nodo insieme a un hashset vuoto

  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

Non ci dovrebbe essere alcun bordo posteriore mentre si fa DFS.Keep traccia dei nodi già visitati mentre si fa DFS, se si incontra un margine tra il nodo corrente e nodo esistente, allora grafico ha ciclo.

Answer 8

: ecco un codice swift per trovare se un grafico ha cicli:

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'idea è simile a questo: un algoritmo di DFS normale con una matrice per tenere traccia dei nodi visitati, e una serie supplementare che serve come un marcatore per i nodi che hanno portato al nodo corrente, in modo che quando mai eseguiamo un DFS per un nodo setteremo la voce corrispondente dell'array marcatore come vero, in modo che quando mai un nodo già visitato rilevato controlliamo se elemento corrispondente nella matrice marcatore è vero, se è vero allora la sua uno dei nodi che permettono a sé (Quindi un ciclo), e il trucco è ogni volta che un DFS di un nodo ritorna abbiamo impostato il suo marcatore corrispondente torna su false, in modo che se abbiamo visitato di nuovo da un altro percorso non fatevi ingannare.

Answer 9

Ecco la mia implementazione rubino del href="http://www.cs.hmc.edu/~keller/courses/cs60/s98/examples/acyclic/" rel="nofollow"> foglia .

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

Appena avuto questa domanda in un'intervista Google.

topologico Ordina

Si può cercare di ordinamento topologicamente, che è O (V + E) dove V è il numero di vertici, e E è il numero di spigoli. Un grafo orientato è aciclico se e solo se questo può essere fatto.

La rimozione ricorsiva Foglia

Il rimuovere in modo ricorsivo nodi foglia fino a quando non ce ne sono di sinistra, e se c'è più di un singolo nodo a sinistra hai un ciclo. A meno che non mi sbaglio, questo è O (V ^ 2 + VE).

DFS-style ~ O (n + m)

Tuttavia, un algoritmo DFS campionature efficiente, caso peggiore O (V + E), è:

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