V prvním stromu s hloubkou jsou hrany definující strom (tj. Hrany, které byly použity v traversal).
Existují některé zbývající hrany spojující některé z ostatních uzlů. Jaký je rozdíl mezi příčnou hranou a přední hranou?
Z wikipedie:
Na základě tohoto překlenovacího stromu jsou hrany původního grafu lze rozdělit do tří tříd: přední hrany, které směřují z uzlu stromu k jednomu z jeho potomků, zadní hrany, které ukazují z uzlu na jednoho z jeho předků, a křížové hrany, které nečiní ani jeden. Někdy jsou hrany stromu, hrany, které patří samotnému kostře, klasifikovány odděleně od předních hran. Pokud je původní graf neorientovaný, pak všechny jeho hrany jsou hranami stromu nebo zadními hranami.
Nehodí se hrana, která se nepoužívá v průchodu, který body z jednoho uzlu do druhého navazují vztah rodič-dítě?
Komentáře
- Související: cs.stackexchange.com/questions/99988/… usiluje o vytvoření algoritmu, který v případě orientovaného grafu bude upřednostňovat vytváření hran dopředu namísto příčných hran během hloubkové vyhledávání.
Odpověď
Wikipedia má odpověď:
Na tomto obrázku se zobrazují všechny typy hran. Vyčleňte DFS v tomto grafu (uzly jsou prozkoumány v číselném pořadí) a podívejte se, kde jsou vaše intuice selže.
Tím se vysvětlí diagram: –
Přední hrana: (u, v), kde v je potomek u, ale ne hrana stromu .Jedná se o nestromovou hranu který spojuje vrchol s potomkem ve stromu DFS.
Cross edge: any other edge. Může přecházet mezi vrcholy ve stejném stromu s hloubkou první nebo v různých stromech s hloubkou první. (laik)
Jde o jakoukoli jinou hranu v grafu G. Spojuje vrcholy ve dvou různých stromech DFS nebo dva vrcholy ve stejném stromu DFS, z nichž žádný není předchůdcem druhého. (formální)
Komentáře
- Proč není nemožné, aby 6 bylo projet jako první (nejprve pravá strana)? Pokud by se to stalo, jak by se nazvala hrana 2- > 3?
- @soandos, navrhuji, abyste si na sledování algoritmu našli čas sami. Za předpokladu, že Wikipedisté ' neudělali chybu, obrázek popisuje bona fide běh DFS v tomto grafu, a tak existuje způsob, jak do této stopy vložit algoritmus. Typy okrajů jsou na Wikipedii popsány dostatečně jasně a můžete si také prohlédnout tento příklad.
- Chápu, že se jedná o platný způsob provedení DFS. Jednoduše se ptám, co kdyby se to stalo opačně.
- Pak by byly výsledky jiné. ' je mi líto, ' musíte to vyřešit sami.
- @soandos Obecně platí, že může být velmi dobře více průchodů DFS. Zde použité pojmy jsou relativní k jednomu danému průchodu a budou se lišit pro více průchodů.
Odpověď
Traverz DFS v neorientovaném grafu nezanechá příčnou hranu, protože jsou prozkoumány všechny hrany, které narážejí na vrchol.
V orientovaném grafu však můžete narazit na hranu který vede k vrcholu, který byl objeven dříve, takže tento vrchol není předkem nebo potomkem aktuálního vrcholu. Takové hraně se říká příčná hrana.
Komentáře
- Aporov, děkuji za odpověď. Stále se mi zdá, že když se dostanete na vrchol 6 v DFS, jak je znázorněno na Wikipedii, máte tři hrany, které musíte projít od 6. V tomto bodě je vrchol 6 " aktuální ". Nakonec přejedete hranu k vrcholu 3. Zatímco 3 již byla navštívena, přesto, že existuje hrana od 6 do 3, pak 3 je potomkem " proudu " vrchol 6. Pokud je tomu tak, porušuje to definici příčného okraje. V definici musí být něco víc, než aby byla ' velmi explicitní.
- Ve skutečnosti obsahuje DFS pouze zadní hrany stromu (Úvod do Algorithms Thm. 22.10).
Odpověď
V průchodu DFS jsou uzly dokončeny, jakmile jsou všechny jejich děti hotovo. Pokud během procházení označíte časy objevení a dokončení pro každý uzel, můžete porovnáním časů zahájení a ukončení zkontrolovat, zda je uzel potomkem. Ve skutečnosti jakýkoli průchod DFS rozdělí jeho okraje podle následujícího pravidla.
Nechť d [uzel] je čas objevení uzlu, stejně tak nechť f [uzel] bude čas dokončení.
Věta závorky Pro všechna u, v platí přesně jedna z následujících možností:
1.d [u] < f [u] < d [v] < f [ v] nebo d [v] < f [v] < d [u] < f [u] a ani jeden z u a v není potomkem druhého.
d [u] < d [v] < f [v] < f [u] a v je potomkem u.
d [v] < d [u] < f [u] < f [v] a u je potomkem v.
Takže d [u] < d [v] < f [u] < f [v] se nemůže stát.
Like závorky: () [], ([]) a [()] jsou v pořádku, ale ([)] a [(]) nejsou v pořádku.
Vezměme si například graf s okraji:
A -> B
A -> C
B -> C
Nechte pořadí návštěvy reprezentovat řetězec popisků uzlů, kde „ABCCBA“ znamená A -> B -> C (dokončeno) B (dokončeno) A (dokončeno), podobně jako ((())).
Takže „ACCBBA“ může být modelem pro „(() ())“.
Příklady:
„CCABBA“: Pak A -> C je křížek hrana, protože CC není uvnitř A.
„ABCCBA“: Pak A -> C je přední hrana (nepřímý potomek).
„ACCBBA“: Pak A -> C je hrana stromu (přímý potomek).
Zdroje:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Poznámky k lákadlům http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm