I ett djup första träd finns det kanterna som definierar trädet (dvs. kanterna som användes i traversal).
Det finns några kvarvarande kanter som förbinder några av de andra noderna. Vad är skillnaden mellan en tvärkant och en framkant?
Från wikipedia:
Baserat på detta spännande träd, kanterna i det ursprungliga diagrammet kan delas in i tre klasser: främre kanter, som pekar från en nod i trädet till en av dess ättlingar, bakre kanter, som pekar från en nod till en av dess förfäder, och tvärkanter, som inte gör något av dem. Ibland klassificeras trädkanter, kanter som tillhör själva det spännande trädet, separat från framkanter. Om originaldiagrammet inte är riktat är alla dess kanter trädkanter eller bakkanter.
Inte en kant som inte används i genomgången som poäng från en nod till en annan upprätta ett förhållande mellan förälder och barn?
Kommentarer
- Relaterat: cs.stackexchange.com/questions/99988/… syftar till att skapa en algoritm som, för riktad graf, föredrar att göra framkanter istället för tvärkanter under djup-första sökning.
Svar
Wikipedia har svaret:
Alla typer av kanter visas i den här bilden. Spåra ut DFS i denna graf (noderna undersöks i numerisk ordning) och se var din intuition misslyckas.
Detta förklarar diagrammet: –
Framkant: (u, v), där v är en ättling till u, men inte en trädkant .Det är en icke-trädkant som ansluter ett toppunkt till en ättling i ett DFS-träd.
Tvärkant: vilken som helst annan kant. Kan gå mellan hörn i samma djup-första träd eller i olika djup-första träd. (lekman)
Det är vilken som helst annan kant i diagram G. Den förbinder hörn i två olika DFS-träd eller två hörn i samma DFS-träd, varav ingen är den förfäder till den andra. (formell)
Kommentarer
- Varför är det inte omöjligt för 6 att ha korsats först (höger sida först)? Om detta hade hänt, vad skulle 2- > 3-kanten ha kallats?
- @soandos, jag föreslår att du tar dig själv att spåra algoritmen. Förutsatt att Wikipedia inte gjorde ett ', beskriver bilden en bona fide-körning av DFS i denna graf, så det finns ett sätt att passa algoritmen i detta spår. Kanterna beskrivs tillräckligt tydligt i Wikipedia, och du kan också se detta exempel.
- Jag förstår att detta är ett giltigt sätt att göra en DFS. Jag frågar helt enkelt vad om det gjordes på andra sidan.
- Då skulle resultaten bli annorlunda. Jag ' jag är ledsen, du ' d måste räkna ut det själv.
- @soandos I allmänhet finns det kan mycket väl vara flera DFS-traversaler. Begreppet som används här är relativt en given traversal och kommer att skilja sig åt för flera traversaler.
Svar
En DFS-traversal i en oriktad graf lämnar inte en tvärkant eftersom alla kanter som inträffar på ett toppunkt utforskas.
I en riktad graf kan du dock komma över en kant som leder till ett toppunkt som har upptäckts tidigare så att toppunktet inte är en förfader eller ättling till det aktuella toppunktet. En sådan kant kallas en tvärkant.
Kommentarer
- Aporov, tack för svaret. Det verkar fortfarande för mig att när du kommer till vertex 6 i DFS som visas i Wikipedia, har du tre kanter att korsa från 6. Vid den punkten är vertex 6 " aktuell ". Så småningom kommer du att korsa kanten till toppunkt 3. Medan 3 redan har besökts, ändå eftersom det finns en kant från 6 till 3, är 3 en ättling till " strömmen " toppunkt 6. Om så är fallet bryter det mot definitionen av en tvärkant. Det måste finnas något mer i definitionen som inte görs ' t mycket tydligt.
- Faktum är att DFS bara innehåller antingen trädkanter för bakkanter (Intro till Algoritmer Thm. 22.10).
Svar
I en DFS-traversal är noder avslutade när alla deras barn är färdiga. Om du markerar upptäckt- och sluttiderna för varje nod under genomkörning kan du kontrollera om en nod är en ättling genom att jämföra start- och sluttider. I själva verket kommer DFS-traversal att dela sina kanter enligt följande regel.
Låt d [nod] vara nodens upptäcktstid, och låt också f [node] vara sluttiden.
Parenthes Theorem För alla u, v gäller exakt ett av följande:
1.d [u] < f [u] < d [v] < f [ v] eller d [v] < f [v] < d [u] < f [u] och ingen av u och v är en ättling till den andra.
d [u] < d [v] < f [v] < f [u] och v är en ättling till u.
d [v] < d [u] < f [u] < f [v] och u är en ättling till v.
Så, d [u] < d [v] < f [u] < f [v] kan inte hända.
Gilla parenteser: () [], ([]) och [()] är OK men ([)] och [(]) är inte OK.
Tänk till exempel på grafen med kanter:
A -> B
A -> C
B -> C
Låt ordningen för besöket representeras av en sträng av noderna, där ”ABCCBA” betyder A -> B -> C (färdig) B (färdig) A (färdig), liknande ((())).
Så ”ACCBBA” kan vara en modell för ”(() ())”.
Exempel:
”CCABBA”: Då är A -> C ett kors kant, eftersom CC inte finns inuti A.
”ABCCBA”: Då är A -> C en framkant (indirekt härkomst).
”ACCBBA”: Då är A -> C en trädkant (direkt ättling).
Källor:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Föreläsningsanteckningar http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm