In een diepte eerste boom zijn er de randen die de boom definiëren (dwz de randen die werden gebruikt in de traversal).
Er zijn enkele overgebleven randen die enkele van de andere knooppunten verbinden. Wat is het verschil tussen een dwarsrand en een voorrand?
Van wikipedia:
Op basis van deze opspannende boom zijn de randen van de oorspronkelijke grafiek kan worden onderverdeeld in drie klassen: voorranden, die van een knooppunt van de boom naar een van zijn nakomelingen wijzen, achterranden, die van een knooppunt naar een van zijn voorouders wijzen, en kruisranden, die geen van beide doen. Soms worden boomranden, randen die bij de opspannende boom zelf horen, apart van voorranden geclassificeerd. Als de originele grafiek niet gericht is, zijn alle randen boomranden of achterranden.
Heeft geen rand die niet wordt gebruikt in de verplaatsing die wijst van het ene knooppunt naar het andere een ouder-kindrelatie tot stand brengen?
Opmerkingen
- Gerelateerd: cs.stackexchange.com/questions/99988/… probeert een algoritme vast te stellen dat, voor gerichte grafieken, de voorkeur geeft aan het maken van voorwaartse randen in plaats van dwarsranden tijdens depth-first search.
Answer
Wikipedia heeft het antwoord:
Alle soorten randen verschijnen in deze afbeelding. Traceer de DFS in deze grafiek (de knooppunten worden in numerieke volgorde verkend) en kijk waar uw intuïtie mislukt.
Dit zal het diagram verklaren: –
Voorwaartse rand: (u, v), waarbij v een afstammeling is van u, maar geen boomrand Het is een niet-boomrand dat een hoekpunt verbindt met een afstammeling in een DFS-boom.
Kruisrand: elke andere rand. Kan tussen hoekpunten in dezelfde diepte-eerste boom of in verschillende diepte-eerst bomen gaan. (leek)
Het is een andere rand in graaf G. Het verbindt hoekpunten in twee verschillende DFS-boom of twee hoekpunten in dezelfde DFS-boom die geen van beide de voorouder is van de andere. (formeel)
Reacties
- Waarom is het niet onmogelijk dat 6 als eerste zijn gepasseerd (rechterkant eerst)? Als dat was gebeurd, wat zou dan de 2- > 3 edge zijn genoemd?
- @soandos, ik stel voor dat je zelf de tijd neemt om het algoritme op te sporen. Ervan uitgaande dat de Wikipedianen geen ‘ een fout hebben gemaakt, beschrijft de afbeelding een bonafide run van DFS in deze grafiek, en er is dus een manier om het algoritme in deze trace te passen. De soorten randen worden duidelijk genoeg beschreven in Wikipedia, en je kunt ook dit voorbeeld raadplegen.
- Ik begrijp dat dit een geldige manier is om een DFS uit te voeren. Ik vraag gewoon wat als het op de andere manier zou gebeuren.
- Dan zouden de resultaten anders zijn. Ik ‘ m sorry, je ‘ zou het zelf moeten uitzoeken.
- @soandos In het algemeen is er kan heel goed meerdere DFS-traversals zijn. De begrippen die hier worden gebruikt, zijn gerelateerd aan een gegeven traversal en zullen verschillen voor meerdere traversals.
Answer
Een DFS-traversal in een ongerichte graaf laat geen kruisrand achter, aangezien alle randen die op een hoekpunt vallen, worden verkend.
In een gerichte graaf kunt u echter een rand tegenkomen dat leidt naar een hoekpunt dat eerder is ontdekt, zodat dat hoekpunt geen voorouder of afstammeling is van het huidige hoekpunt. Zon rand wordt een cross edge genoemd.
Reacties
- Aporov, bedankt voor de reactie. Het lijkt me nog steeds dat wanneer je bij hoekpunt 6 in de DFS komt, zoals weergegeven in Wikipedia, je drie randen hebt om van 6 af te steken. Op dat punt is hoekpunt 6 ” actueel “. Uiteindelijk ga je de rand oversteken naar hoekpunt 3. Hoewel 3 al bezocht is, maar omdat er een rand is van 6 naar 3, is 3 een afstammeling van de ” stroom ” hoekpunt 6. Als dat zo is, schendt het de definitie van een dwarsrand. Er moet iets meer aan de definitie zijn dat niet ‘ t erg expliciet wordt gemaakt.
- In feite bevat DFS alleen boomranden voor achterranden (Inleiding tot Algoritmen Thm. 22.10).
Antwoord
In een DFS-traversal zijn knooppunten klaar zodra al hun kinderen zijn afgewerkt. Als u de ontdek- en eindtijden voor elk knooppunt tijdens het doorlopen markeert, kunt u controleren of een knooppunt een afstammeling is door begin- en eindtijden te vergelijken. In feite zal elke DFS-doorgang zijn randen partitioneren volgens de volgende regel.
Laat d [knooppunt] de ontdekkingstijd van knooppunt zijn, en laat evenzo f [knooppunt] de eindtijd zijn.
Stelling tussen haakjes Voor alle u, v geldt precies een van de volgende:
1.d [u] < f [u] < d [v] < f [ v] of d [v] < f [v] < d [u] < f [u] en geen van beide is een afstammeling van de ander.
d [u] < d [v] < f [v] < f [u] en v is een afstammeling van u.
d [v] < d [u] < f [u] < f [v] en u is een afstammeling van v.
Dus d [u] < d [v] < f [u] < f [v] kan niet gebeuren.
Vind ik leuk haakjes: () [], ([]) en [()] zijn OK, maar ([)] en [(]) zijn niet OK.
Beschouw bijvoorbeeld de grafiek met randen:
A -> B
A -> C
B -> C
Laat de volgorde van bezoeken worden weergegeven door een reeks van de knooppuntenlabels, waarbij “ABCCBA” betekent A -> B -> C (voltooid) B (voltooid) A (voltooid), vergelijkbaar met ((())).
Dus “ACCBBA” zou een model kunnen zijn voor “(() ())”.
Voorbeelden:
“CCABBA”: Dan is A -> C een kruising edge, aangezien de CC niet binnen A is.
“ABCCBA”: Dan is A -> C een voorste rand (indirecte afstammeling).
“ACCBBA”: Dan is A -> C een boomrand (directe afstammeling).
Bronnen:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Lecure Notes http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm