Dato un albero di spanning e un bordo non sull'albero di spanning, come formare una base di ciclo?

Question

Ho un grafico con Edge E e Vertice V, posso trovare l'albero di spanning usando Algoritmo di Kruskal (o qualsiasi altro tipo di algoritmo traverse-backtrack-traverse-again), ora voglio trovare tutte le basi del ciclo che vengono create utilizzando quell'albero di spanning e i bordi che non sono sul albero, qualche algoritmo che mi permette di farlo, oltre alla ricerca della forza bruta?

Ovviamente posso partire da un vertice del bordo dell'albero non spanning, ottenere tutti i bordi, esplorarli tutti, ritrarre se trovo un vicolo cieco, fino a quando non torno all'altro vertice del bordo. Ma questo è un po ', err ... brutale. Altre idee?

Answer 1

Un semplice algoritmo che usiamo per trovare cicli nei grafici:

  

Crea un albero di spanning in profondità   dove ogni nodo ha un genitore.       Attraversando l'albero creare un record di nodi usati.       Quando un bordo punta a un nodo precedentemente utilizzato, memorizzarlo come a   bordo ciclico.       Quando l'albero di spanning è completo, il conteggio del ciclico   bordi dà il conteggio dei cicli.       Per ogni fronte ciclica recidere attraverso gli antenati dei due nodi   fino a quando non viene trovato un antenato comune. Quello   fornirà esattamente i cicli.

Può essere utile avere un indice (hashtable) di tutti gli antenati di un nodo di bordo ciclico in modo che sia rapido trovare l'antenato comune.

Dubito che questo sia l'algoritmo migliore ma è abbastanza veloce.

MODIFICA in risposta al commento Ogni nodo nella spanning tree ha un genitore. Quando viene raggiunto un nodo in un bordo ciclico, calcola il suo elenco di antenati (List<Node> Questo elenco può essere indicizzato per la velocità (ovvero contiene () è < O(n)). Quando viene trovato un bordo ciclico con due nodi (n1, n2) iterare attraverso gli antenati di n1, n1.ancestorList (rapidamente poiché l'elenco è già stato creato) e verificare se l'antenato si trova in n2.ancestorList. Se lo è (commonAncestor), allora esattamente quegli antenati attraversati corrispondono ai cicli. Quindi scorrere n2 fino a raggiungere O(logN) (rapido). Il tempo dovrebbe dipendere dal numero di spigoli ciclici, combinato con la ricerca negli elenchi (probabilmente <=> ma economico). Non è necessario riesplorare il grafico e non c'è nessun backtracking.

Answer 2

Dopo aver costruito lo spanning tree, iterare su ogni spigolo (A, B) che non si trova nell'albero e trovare Lowest Common Ancestor (LCA) per i nodi di questo spigolo, il ciclo sarà percorso da A - & Gt; LCA - & Gt; B - & Gt; A

puoi usare questo link: http: //www.topcoder .com / TC module = Statico amp? &; d1 = tutorial amp &; d2 = lowestCommonAncestor     per un'implementazione efficiente dell'algoritmo Ancestor più basso.