Come verificare se v'è un cerchio in un albero?

Question

Ecco un albero:

  

  

1. Ci sarà una radice.

  

2. Ogni nodo della struttura ha zero o più figli.

  

3. E 'consentito che due nodi punti per lo stesso bambino. Per esempio, sia il nodo A   e il nodo B ha bambino C.

  

Tuttavia, è vietato che,

  

Il nodo A è un discendente del Nodo B, e   Nodo B è un discendente del nodo A.

Un caso fermo il divieto è

  

Un nodo ha un figlio Nodo C e Nodo D,

     

Sia Nodo C e D ha un nodo figlio E,

     

Il nodo E ha un figlio di A.

La domanda è: come determinare questo cerchio in modo più veloce?

Aggiorna : Mi rendo conto che è quello di trovare qualsiasi ciclo in un grafo orientato. Poco fa sono riuscito a pensare una soluzione simile a algoritmo di Tarjan.

Grazie per i commenti.

Answer 1

Fare un ricerca in profondità attraverso l'albero. Se in qualsiasi momento a trovare un nodo che è già nel tuo stack backtracking, c'è un cerchio.

Answer 2

cerchi possono essere trovati utilizzando 2 puntatori e li avanza ad intervalli differenti. Alla fine i puntatori corrisponderanno, indicando un ciclo, o il "più veloce" uno raggiungeranno poi fine. La domanda è di solito chiesto di liste collegate, però, non gli alberi.