I et dybde første træ er der kanterne, der definerer træet (dvs. de kanter, der blev brugt i traversal).
Der er nogle resterende kanter, der forbinder nogle af de andre noder. Hvad er forskellen mellem en tværkant og en fremadgående kant?
Fra wikipedia:
Baseret på dette spændende træ er kanterne af den oprindelige graf kan opdeles i tre klasser: forreste kanter, der peger fra en knude på træet til en af dets efterkommere, bagkanter, der peger fra en knude til en af dens forfædre, og tværkanter, som ingen af dem gør. Undertiden klassificeres trækanter, kanter, der hører til selve det spændende træ, separat fra forkant. Hvis den oprindelige graf ikke er rettet, er alle kanterne trækanter eller bagkanter.
Er det ikke en kant, der ikke bruges i traversen, som punkter fra en node til en anden etablere et forhold mellem forældre og børn?
Kommentarer
- Relateret: cs.stackexchange.com/questions/99988/… søger at etablere en algoritme, der for rettet graf foretrækker at lave forreste kanter i stedet for tværkanter under dybde-første søgning.
Svar
Wikipedia har svaret:
Alle typer kanter vises på dette billede. Spor DFS ud på denne graf (noderne udforskes i numerisk rækkefølge), og se hvor din intuition mislykkes.
Dette forklarer diagrammet: –
Fremad: (u, v), hvor v er en efterkommer af u, men ikke en trækant .Det er en ikke-trækant der forbinder et toppunkt med en efterkommer i et DFS-træ.
Tværkant: enhver anden kant. Kan gå mellem hjørner i samme dybde-første træ eller i forskellige dybde-første træer. (lægmand)
Det er en hvilken som helst anden kant i graf G. Det forbinder hjørner i to forskellige DFS-træ eller to hjørner i samme DFS-træ, hvor ingen af dem er forfader til den anden. (formel)
Kommentarer
- Hvorfor er det ikke umuligt for 6 at have været krydset først (højre side først)? Hvis dette var sket, hvad ville 2- > 3-kanten være blevet kaldt?
- @soandos, jeg foreslår, at du tager dig selv tid til at spore algoritmen. Forudsat at Wikipediaerne ikke ‘ ikke begik en fejl, beskriver billedet en bona fide-kørsel af DFS på denne graf, og der er således en måde at passe algoritmen ind i dette spor. Typerne af kanter er beskrevet tydeligt nok i Wikipedia, og du kan også se dette eksempel.
- Jeg forstår, at dette er en gyldig måde at lave en DFS på. Jeg spørger simpelthen, hvad hvis det blev gjort den anden vej.
- Så ville resultaterne være forskellige. Jeg ‘ undskyld, du ‘ d skal selv finde ud af det.
- @soandos Generelt er der kan meget vel være flere DFS-traversaler. Begreberne her er relative til en given traversal og vil variere for flere traversaler.
Svar
En DFS-traversal i en ikke-rettet graf efterlader ikke en tværkant, da alle kanter, der er indfaldende på et toppunkt, udforskes.
I en rettet graf kan du dog støde på en kant der fører til et toppunkt, der er blevet opdaget før, således at toppunktet ikke er en forfader eller efterkommer af det aktuelle toppunkt. En sådan kant kaldes en tværkant.
Kommentarer
- Aporov, tak for svaret. For mig ser det stadig ud til, at når du kommer til toppunkt 6 i DFS som vist i Wikipedia, har du tre kanter at krydse fra 6. På det tidspunkt er toppunkt 6 ” nuværende “. Til sidst skal du krydse kanten til toppunkt 3. Mens 3 allerede er besøgt, ikke desto mindre da der er en kant fra 6 til 3, så er 3 en efterkommer af ” strøm ” toppunkt 6. Hvis det er tilfældet, overtræder det definitionen af en tværkant. Der skal være noget mere ved definitionen, der ikke ‘ t gøres meget eksplicit.
- Faktisk indeholder DFS kun begge trækanter til bagkanter (Intro til Algoritmer Thm. 22.10).
Svar
I en DFS-traversal er noder færdige, når alle deres børn er færdig. Hvis du markerer opdagelses- og sluttiderne for hver node under gennemkørsel, kan du kontrollere, om en node er en efterkommer ved at sammenligne start- og sluttider. Faktisk vil enhver DFS-traversal opdele sine kanter i henhold til følgende regel.
Lad d [node] være opdagelsestidspunktet for node, ligesom f [node] skal være sluttid.
Parenthes Theorem For alle u, v gælder nøjagtigt et af følgende:
1.d [u] < f [u] < d [v] < f [ v] eller d [v] < f [v] < d [u] < f [u] og ingen af u og v er en efterkommer af den anden.
d [u] < d [v] < f [v] < f [u] og v er en efterkommer af u.
d [v] < d [u] < f [u] < f [v] og u er en efterkommer af v.
Så, d [u] < d [v] < f [u] < f [v] kan ikke ske.
Synes godt om parenteser: () [], ([]) og [()] er OK, men ([)] og [(]) er ikke OK.
Overvej f.eks. grafen med kanter:
A -> B
A -> C
B -> C
Lad rækkefølgen for besøget repræsenteres af en streng af knudepunkter, hvor “ABCCBA” betyder A -> B -> C (færdig) B (færdig) A (færdig), svarende til ((())).
Så “ACCBBA” kan være en model for “(() ())”.
Eksempler:
“CCABBA”: Så er A -> C et kryds kant, da CC ikke er inde i A.
“ABCCBA”: Så er A -> C en forreste kant (indirekte efterkommer).
“ACCBBA”: Så er A -> C en trækant (direkte efterkommer).
Kilder:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Forelæsningsnotater http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm