Perché DFS e non BFS per trovare il ciclo nei grafici

Prevalentemente DFS viene utilizzato per trovare un ciclo nei grafici e non in BFS. Qualche motivo? Entrambi possono scoprire se un nodo è già stato visitato mentre si attraversa l’albero / grafico.

La prima ricerca della profondità è più efficiente in termini di memoria rispetto alla prima ricerca, in quanto è ansible tornare indietro di prima. È anche più facile da implementare se si utilizza lo stack di chiamate, ma questo si basa sul percorso più lungo che non trabocca dallo stack.

Inoltre, se il tuo grafico è diretto, non devi semplicemente ricordare se hai visitato un nodo o meno, ma anche come ci sei arrivato. Altrimenti potresti pensare di aver trovato un ciclo ma in realtà tutto ciò che hai sono due percorsi separati A-> B ma ciò non significa che ci sia un percorso B-> A. Per esempio,

Se fai BFS a partire da 0 , rileverà come il ciclo è presente ma in realtà non esiste un ciclo.

Con una prima ricerca di profondità è ansible contrassegnare i nodes visitati mentre si scende e deselezionarli mentre si fa il backtrack. Vedere i commenti per un miglioramento delle prestazioni su questo algoritmo.

Per il miglior algoritmo per il rilevamento dei cicli in un grafico diretto è ansible osservare l’algoritmo di Tarjan .

  1. DFS è più facile da implementare
  2. Una volta che DFS trova un ciclo, lo stack conterrà i nodes che formano il ciclo. Lo stesso non vale per BFS, quindi è necessario fare del lavoro extra se si desidera stampare anche il ciclo trovato. Questo rende DFS molto più conveniente.

Un BFS potrebbe essere ragionevole se il grafo non è orientato (sii mio ospite a mostrare un algoritmo efficiente usando BFS che riporterebbe i cicli in un grafo diretto!), Dove ogni “cross edge” definisce un ciclo. Se il cross-edge è {v1, v2} , e la radice (nell’albero BFS) che contiene quei nodes è r , allora il ciclo è r ~ v1 - v2 ~ r ( ~ è un percorso, - un singolo spigolo), che può essere segnalato quasi facilmente come in DFS.

L’unico motivo per utilizzare un BFS sarebbe se si sapesse che il proprio grafico (non orientato) avrà percorsi lunghi e copertura del percorso piccolo (in altre parole, profondo e stretto). In tal caso, BFS richiederebbe proporzionalmente meno memoria per la sua coda rispetto allo stack di DFS (entrambi ovviamente lineari).

In tutti gli altri casi, DFS è chiaramente il vincitore. Funziona su entrambi i grafici diretti e non orientati, ed è banale riportare i cicli – basta concatenare qualsiasi margine posteriore al percorso dall’antenato al discendente, e si ottiene il ciclo. Tutto sumto, molto meglio e pratico di BFS per questo problema.

Se si posiziona un ciclo in un punto casuale in un albero, il DFS tenderà a colpire il ciclo quando viene coperto circa metà dell’albero e metà del tempo che avrà già percorso dove va il ciclo e metà del tempo in cui non lo farà ( e lo troverà in media a metà del resto dell’albero), quindi valuterà in media circa 0,5 * 0,5 + 0,5 * 0,75 = 0,625 dell’albero.

Se posizioni un ciclo in un punto casuale in un albero, BFS tenderà a colpire il ciclo solo quando viene valutato il livello dell’albero a quella profondità. Quindi, di solito finisci per dover valutare le foglie di un albero binario di equilibrio, che generalmente si traduce nella valutazione di più dell’albero. In particolare, 3/4 delle volte almeno uno dei due link appare nelle foglie dell’albero, e in questi casi devi valutare in media 3/4 dell’albero (se c’è un link) o 7 / 8 dell’albero (se ce ne sono due), quindi stai già aspettando una ricerca 1/2 * 3/4 ​​+ 1/4 * 7/8 = (7 + 12) / 32 = 21/32 = 0,656 … dell’albero senza nemmeno aggiungere il costo della ricerca di un albero con un ciclo aggiunto lontano dai nodes foglia.

Inoltre, DFS è più facile da implementare rispetto a BFS. Quindi è quello da usare a meno che tu non sappia qualcosa sui tuoi cicli (ad esempio, i cicli sono probabilmente vicini alla radice da cui cerchi, a quel punto BFS ti dà un vantaggio).

BFS non funzionerà per un grafico diretto nella ricerca di cicli. Considerare A-> B e A-> C-> B come percorsi da A a B in un grafico. BFS dirà che dopo aver seguito uno dei percorsi che B viene visitato. Quando si continua a percorrere il prossimo percorso, si dirà che il nodo contrassegnato B è stato nuovamente trovato, quindi, c’è un ciclo. Chiaramente non c’è nessun ciclo qui.

Per dimostrare che un grafico è ciclico è sufficiente dimostrare che ha un ciclo (il bordo punta verso se stesso direttamente o indirettamente).

In DFS prendiamo un vertice alla volta e controlliamo se ha un ciclo. Non appena viene trovato un ciclo, possiamo omettere di controllare altri vertici.

In BFS abbiamo bisogno di tenere traccia di molti bordi dei vertici simultaneamente e più spesso che no alla fine si scopre se ha un ciclo. All’aumentare della dimensione del grafico, BFS richiede più spazio, calcolo e tempo rispetto a DFS.

Dipende se si parla di implementazioni ricorsive o iterative.

DFS ricorsivo visita due volte ogni nodo. Iterative-BFS visita ogni nodo una sola volta.

Se vuoi rilevare un ciclo, devi indagare sui nodes sia prima che dopo aver aggiunto le loro adiacenze – sia quando “inizi” su un nodo e quando “finisci” con un nodo.

Ciò richiede più lavoro in Iterative-BFS, quindi molte persone scelgono Recursive-DFS.

Si noti che una semplice implementazione di Iterative-DFS con, diciamo, std :: stack ha lo stesso problema di Iterative-BFS. In tal caso, è necessario inserire elementi fittizi nello stack per tracciare quando “finisci” di lavorare su un nodo.

Vedi questa risposta per maggiori dettagli su come Iterative-DFS richiede lavoro aggiuntivo per determinare quando “finisci” con un nodo (risposta nel contesto di TopoSort):

Ordinamento topologico mediante DFS senza ricorsione

Speriamo che questo spieghi perché le persone preferiscono Recursive-DFS per i problemi in cui è necessario determinare quando “finisci” l’elaborazione di un nodo.