I et dybde første tre er det kantene som definerer treet (dvs. kantene som ble brukt i traversal).
Det er noen resterende kanter som forbinder noen av de andre nodene. Hva er forskjellen mellom en tverrkant og en fremkant?
Fra wikipedia:
Basert på dette spennende treet, er kantene av den opprinnelige grafen kan deles inn i tre klasser: fremre kanter, som peker fra en node av treet til en av etterkommerne, bakkantene, som peker fra en node til en av dens forfedre, og tverrkanter, som ikke gjør noen av dem. Noen ganger klassifiseres trekantene, kanter som tilhører selve det spennende treet, separat fra fremkantene. Hvis den opprinnelige grafen ikke er rettet, er alle kantene trekanter eller bakkanter.
Har det ikke en kant som ikke brukes i traversalen som poeng fra en node til en annen etablere et foreldre-barn forhold?
Kommentarer
- Relatert: cs.stackexchange.com/questions/99988/… søker å etablere en algoritme som, for rettet graf, foretrekker å lage fremre kanter, i stedet for tverrkanter, under dybde-første søk.
Svar
Wikipedia har svaret:
Alle typer kanter vises i dette bildet. Spor ut DFS i denne grafen (nodene blir utforsket i numerisk rekkefølge), og se hvor din intuisjonen mislykkes.
Dette vil forklare diagrammet: –
Fremkant: (u, v), der v er en etterkommer av u, men ikke en trekant .Det er en ikke-trekant som forbinder et toppunkt til en avstamning i et DFS-tre.
Tverrkant: hvilken som helst annen kant. Kan gå mellom hjørner i samme dybde-første tre eller i forskjellige dybde-første trær. (lekmann)
Det er en hvilken som helst annen kant i graf G. Den forbinder hjørner i to forskjellige DFS-tre eller to hjørner i samme DFS-tre som ingen er forfedre til den andre. (formell)
Kommentarer
- Hvorfor er det ikke umulig for 6 å ha blitt krysset først (høyre side først)? Hvis det hadde skjedd, hva ville 2- > 3-kanten blitt kalt?
- @soandos, jeg foreslår at du tar deg tid til å spore algoritmen. Forutsatt at Wikipedia ikke ' ikke gjorde en feil, beskriver bildet en bona fide run av DFS på denne grafen, og det er derfor en måte å passe algoritmen inn i dette sporet. Kanttypene er beskrevet tydelig nok i Wikipedia, og du kan også se dette eksemplet.
- Jeg forstår at dette er en gyldig måte å gjøre en DFS på. Jeg spør ganske enkelt hva om det ble gjort den andre veien.
- Da ville resultatene blitt forskjellige. Jeg ' beklager, du ' d må ordne det selv.
- @soandos Generelt er det kan veldig godt være flere DFS-traversaler. Begrepene som brukes her er i forhold til en gitt traversal og vil variere for flere traversaler.
Svar
En DFS-traversering i en ikke-rettet graf etterlater ikke en tverrkant siden alle kanter som rammer et toppunkt blir utforsket.
I en rettet graf kan du imidlertid komme over en kant som fører til et toppunkt som har blitt oppdaget før slik at toppunktet ikke er en forfader eller etterkommer av dagens toppunkt. En slik kant kalles en tverrkant.
Kommentarer
- Aporov, takk for svaret. Fortsatt virker det for meg at når du kommer til toppunkt 6 i DFS som skissert på Wikipedia, har du tre kanter å krysse fra 6. På det punktet er toppunkt 6 " nåværende ". Til slutt skal du krysse kanten til toppunkt 3. Mens 3 allerede er besøkt, men siden det er en kant fra 6 til 3, er 3 en etterkommer av " strømmen " toppunkt 6. Hvis det er slik, bryter det definisjonen av en tverrkant. Det må være noe mer i definisjonen som ikke blir ' t veldig eksplisitt.
- Faktisk inneholder DFS bare en av trekantene for bakkantene (Intro til Algoritmer Thm. 22.10).
Svar
I en DFS-traversal er noder ferdig når alle barna deres er ferdig. Hvis du markerer oppdagelses- og sluttidene for hver node under traversering, kan du sjekke om en node er en etterkommer ved å sammenligne start- og sluttider. Faktisk vil enhver DFS-traversering partisjonere kantene i henhold til følgende regel.
La d [node] være oppdagelsestiden for noden, og la f [node] være sluttid.
Parenthes Theorem For alle u, v, gjelder nøyaktig ett av følgende:
1.d [u] < f [u] < d [v] < f [ v] eller d [v] < f [v] < d [u] < f [u] og ingen av u og v er en etterkommer av den andre.
d [u] < d [v] < f [v] < f [u] og v er en etterkommer av u.
d [v] < d [u] < f [u] < f [v] og u er en etterkommer av v.
Så, d [u] < d [v] < f [u] < f [v] kan ikke skje.
Liker parenteser: () [], ([]) og [()] er OK, men ([)] og [(]) er ikke OK.
Tenk for eksempel på grafen med kanter:
A -> B
A -> C
B -> C
La rekkefølgen på besøk være representert av en streng av nodene, der «ABCCBA» betyr A -> B -> C (ferdig) B (ferdig) A (ferdig), lik ((())).
Så «ACCBBA» kan være en modell for «(() ())».
Eksempler:
«CCABBA»: Da er A -> C et kryss kant, siden CC ikke er inne i A.
«ABCCBA»: Da er A -> C en fremkant (indirekte etterkommer).
«ACCBBA»: Da er A -> C en trekant (direkte etterkommer).
Kilder:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Forelesningsnotater http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm