Come rilevare se un grafo orientato è ciclica?

Question

Come possiamo rilevare se un grafo orientato è ciclica? Ho pensato che utilizzando ricerca in ampiezza, ma non sono sicuro. Qualche idea?

Answer 1

Ricerca Di solito in profondità è usato al posto. non so se BFS è applicabile facilmente.

DFS , un albero di copertura è costruito in modo di visitare. Se un l'antenato di un nodo nell'albero è visitato (cioè si crea un back-bordo), quindi si rileva un ciclo.

http: // www .cs.nyu.edu / corsi / summer04 / G22.1170-001 / 6a-grafici-More.pdf per una spiegazione più dettagliata.

Answer 2

Quello che si ha realmente bisogno, credo, è un algoritmo di ordinamento topologico come quello descritto qui:

http://en.wikipedia.org/wiki/Topological_sorting

Se il grafo orientato ha un ciclo allora l'algoritmo sicuro.

I commenti / risposte che ho visto finora sembrano mancare il fatto che in un diretto grafico ci può essere più di un modo per ottenere dal nodo X al nodo Y senza che vi sia eventuali (diretto) cicli nel grafico.

Answer 3

Usa DFS per cercare se qualsiasi percorso è ciclica

class Node<T> { T value; List<Node<T>> adjacent;  }

class Graph<T>{

    List<Node<T>> nodes;

   public boolean isCyclicRec()
   {

      for (Node<T> node : nodes)
      {
            Set<Node<T>> initPath = new HashSet<>();
            if (isCyclicRec(node, initPath))
            {
              return true;
            }
      }
      return false;
   }

   private boolean isCyclicRec(Node<T> currNode, Set<Node<T>> path)
   {
      if (path.contains(currNode))
      {
        return true;
      }
      else
      {
        path.add(currNode);
        for (Node<T> node : currNode.adjacent)
        {
            if (isCyclicRec(node, path))
            {
                return true;
            }
            else
            {
                path.remove(node);
            }
        }
      }
      return false;
  }

Answer 4

approccio: 1
Che ne dite di un livello nessuna assegnazione per rilevare un ciclo. es: considerare il grafico sottostante. A -> (B, C) B-> D D -> (E, F) E, F -> (G) E-> D Come si esegue un DFS iniziare l'assegnazione di un livello non al nodo che si visita (root A = 0). NESSUNO di nodo genitore = + 1. Quindi A = 0, B = 1, D = 2, F = 3, G = 4 quindi, raggiunge ricorsione D, quindi E = 3. Dont livello di marchio per G (G già un livello non assegnato che è grattugia di E) Ora E ha anche un vantaggio per D. Quindi levelization direbbe D dovrebbe ottenere un livello non di 4. Ma D ha già un "livello più basso" assegnato ad esso di 2. Così ogni volta che si tenta di assegnare un numero di livello ad un nodo mentre si fa DFS che ha già un numero di livello più basso impostato ad esso, si conosce il grafo orientato ha un ciclo ..

approach2:
usare 3 colori. bianco, grigio, nero. colore solo i nodi bianchi, i nodi bianco al grigio, come si va giù per la DFS, colore nodi grigio al nero quando si svolge la ricorsione (tutti i bambini sono trattati). se non tutti i bambini ancora elaborati e si colpisce un nodo grigio questo è un ciclo. es: tutto bianco per iniziare supra grafico diretta. colore A, B, D, F, G sono di colore bianco-grigio. G è foglia in modo che tutti i bambini di colore elaborati è grigio al nero. ricorsione si svolge a F (tutti i bambini trattati) colorare di nero. ora si raggiunge D, D ha figli non trasformati, quindi di colore grigio E, G già colorato di nero in modo da non andare più in basso. E ha anche bordo a D, così mentre ancora elaborando D (D ancora grigio), si trova un bordo posteriore a D (un nodo grigio), viene rilevato un ciclo.

Answer 5

Test per l'ordinamento topologico sopra il dato grafo vi condurrà alla soluzione. Se l'algoritmo per topsort, cioè i bordi devono essere rivolti sempre in un modo fallisce, allora significa che il grafico contiene cicli.

Answer 6

Un'altra soluzione semplice sarebbe un approccio mark-and-sweep. In pratica, per ogni nodo dell'albero si contrassegna come "visitato" e poi passare al suo bambino. Se avete mai visto un nodo con il "visted" flag impostato, sapete che c'è un ciclo.

Se modificando i dati per includere un po ' "visitato" non è possibile, un insieme di puntatori nodo può essere usato al posto. Per contrassegnare un nodo come ha visitato, si inserisce un puntatore ad esso nel set. Se il puntatore è già nel set, c'è un ciclo.