In un primo albero di profondità, ci sono i bordi che definiscono lalbero (cioè i bordi che sono stati usati nel traversal).
Ci sono alcuni bordi rimanenti che collegano alcuni degli altri nodi. Qual è la differenza tra un bordo trasversale e un bordo anteriore?
Da wikipedia:
Sulla base di questo albero spanning, i bordi del grafo originale può essere diviso in tre classi: bordi anteriori, che puntano da un nodo dellalbero a uno dei suoi discendenti, bordi posteriori, che puntano da un nodo a uno dei suoi antenati, e bordi incrociati, che non fanno nessuno dei due. A volte i bordi degli alberi, i bordi che appartengono allo spanning tree stesso, sono classificati separatamente dai bordi anteriori. Se il grafico originale non è orientato, tutti i suoi bordi sono bordi dellalbero o bordi posteriori.
Non è un bordo che non è utilizzato nellattraversamento che punti da un nodo a un altro stabilire una relazione genitore-figlio?
Commenti
- Correlati: cs.stackexchange.com/questions/99988/… cerca di stabilire un algoritmo che, per il grafo diretto, preferirà creare bordi in avanti, invece di bordi incrociati, durante ricerca approfondita.
Risposta
Wikipedia ha la risposta:
Tutti i tipi di bordi appaiono in questa immagine. Traccia DFS su questo grafico (i nodi sono esplorati in ordine numerico) e guarda dove il tuo lintuizione fallisce.
Questo spiegherà il diagramma: –
Bordo in avanti: (u, v), dove v è un discendente di u, ma non il bordo di un albero .È un bordo non albero che collega un vertice a un discendente in un albero DFS.
Spigolo incrociato: qualsiasi altro spigolo. Può passare tra i vertici nello stesso albero con prima profondità o in alberi con prima profondità diversi. (laico)
È qualsiasi altro bordo nel grafo G. Collega i vertici in due diversi alberi DFS o due vertici nello stesso albero DFS nessuno dei quali è lantenato dellaltro. (formale)
Commenti
- Perché non è impossibile che 6 siano stati attraversati per primi (prima il lato destro)? Se ciò fosse accaduto, come sarebbe stato chiamato il 2- > 3 edge?
- @soandos, ti suggerisco di prenderti il tempo per tracciare lalgoritmo. Supponendo che i wikipediani non abbiano ‘ commesso un errore, limmagine descrive una corsa in buona fede di DFS su questo grafico, quindi cè un modo per adattare lalgoritmo in questa traccia. I tipi di bordi sono descritti abbastanza chiaramente in Wikipedia e puoi anche consultare questo esempio.
- Capisco che questo sia un modo valido per fare un DFS. Sto semplicemente chiedendo cosa succede se è stato fatto in un altro modo.
- Allora i risultati sarebbero diversi. Mi ‘ Mi dispiace, ‘ dovresti risolverlo da solo.
- @soandos In generale, lì può benissimo essere più attraversamenti DFS. Le nozioni qui utilizzate sono relative a un dato attraversamento e differiranno per più attraversamenti.
Risposta
Un attraversamento DFS in un grafo non orientato non lascerà un bordo incrociato poiché vengono esplorati tutti i bordi incidenti su un vertice.
Tuttavia, in un grafico orientato, potresti imbatterti in un bordo che porta a un vertice che è stato scoperto prima tale che quel vertice non è un antenato o un discendente del vertice corrente. Tale margine è chiamato margine trasversale.
Commenti
- Aporov, grazie per la risposta. Mi sembra ancora che quando arrivi al vertice 6 nel DFS come illustrato in Wikipedia, hai tre lati da attraversare da 6. A quel punto, il vertice 6 è ” corrente “. Alla fine attraverserai il bordo fino al vertice 3. Sebbene 3 sia già stato visitato, tuttavia poiché cè un bordo da 6 a 3, 3 è un discendente della corrente ” ” vertice 6. Se è così, viola la definizione di bordo trasversale. Deve esserci qualcosaltro nella definizione che ‘ non viene reso molto esplicito.
- In effetti, DFS contiene solo entrambi i bordi dellalbero per i bordi posteriori (Introduzione a Algoritmi Thm. 22.10).
Risposta
In un attraversamento DFS, i nodi sono finiti una volta che tutti i loro figli sono finito. Se contrassegni i tempi di scoperta e di fine per ogni nodo durante lattraversamento, puoi verificare se un nodo è un discendente confrontando i tempi di inizio e di fine. Infatti qualsiasi attraversamento DFS partizionerà i suoi bordi in base alla seguente regola.
Sia d [nodo] il tempo di scoperta del nodo, allo stesso modo sia f [nodo] lora di fine.
Teorema delle parentesi Per tutti u, v, vale esattamente una delle seguenti:
1.d [u] < f [u] < d [v] < f [ v] o d [v] < f [v] < d [u] < f [u] e nessuno di ue v è un discendente dellaltro.
d [u] < d [v] < f [v] < f [u] ev è un discendente di u.
d [v] < d [u] < f [u] < f [v] eu è un discendente di v.
Quindi, d [u] < d [v] < f [u] < f [v] non può accadere.
Mi piace parentesi: () [], ([]) e [()] sono OK ma ([)] e [(]) non sono OK.
Ad esempio, considera il grafico con i bordi:
A -> B
A -> C
B -> C
Lascia che lordine di visita sia rappresentato da una stringa delle etichette dei nodi, dove “ABCCBA” significa A -> B -> C (finito) B (finito) A (finito), simile a ((())).
Quindi “ACCBBA” potrebbe essere un modello per “(() ())”.
Esempi:
“CCABBA”: Allora A -> C è una croce bordo, poiché CC non è allinterno di A.
“ABCCBA”: Allora A -> C è un bordo anteriore (discendente indiretto).
“ACCBBA”: Allora A -> C è un bordo albero (discendente diretto).
Fonti:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Note Lecure http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm