Az első mélységű fában ott vannak az élek, amelyek meghatározzák a fát (vagyis azokat az éleket, amelyeket a bejárása).
Van néhány megmaradt él, amely összeköti a többi csomópontot. Mi a különbség a keresztszél és az elülső él között?
A wikipédiából:
Ezen átívelő fa alapján az élek Az eredeti gráf három osztályba sorolható: elülső élek, amelyek a fa egy csomópontjától az egyik leszármazottjáig mutatnak, hátsó élek, amelyek egy csomóponttól egyik őse felé mutatnak, és keresztirányú élek, amelyek egyiket sem. Előfordul, hogy a faszegélyeket, a széleket, amelyek magához a fához tartoznak, külön osztályozzuk az elülső élektől. Ha az eredeti grafikon irányítatlan, akkor annak minden éle fa vagy hátsó él.
Nem használ olyan élt, amelyet nem használnak az az egyik csomópontról a másikra mutató pontok létrehozzák a szülő-gyermek kapcsolatot?
Megjegyzések
- Kapcsolódó: A cs.stackexchange.com/questions/99988/… algoritmus létrehozására törekszik, amely az irányított gráfhoz a keresztmetszetek helyett inkább az éleket kívánja előállítani mélység-első keresés.
Válasz
A Wikipédiának megvan a válasza:
Az élek minden típusa megjelenik a képen. Kövesse ki a DFS-t ezen a grafikonon (a csomópontokat numerikus sorrendben tárja fel), és nézze meg, hol az intuíció kudarcot vall.
Ez megmagyarázza a diagramot: –
Elülső él: (u, v), ahol v az u leszármazottja, de nem faszél .Ez nem fa széle amely összeköti a csúcsot egy DFS-fa leszármazottjával.
Kereszt: minden más él. Lehet haladni a csúcsok között ugyanabban a mélységben, vagy különböző mélységben lévő fákban. (laikus)
Ez egy másik él a G gráfban. Két különböző DFS-fában lévő csúcsokat vagy ugyanazon DFS-fában lévő két csúcsot köti össze, amelyek egyikének sem őse a másik. (formális)
Megjegyzések
- Miért nem lehetetlen, hogy 6-ot elsőként (jobb oldalt először) haladtak át? Ha ez megtörtént, hogyan hívták volna meg a 2- > 3 élt?
- @soandos, azt javaslom, hogy szánjon magának időt az algoritmus felkutatására. Feltételezve, hogy a wikipédiek nem hibáztak ‘, a kép a DFS jóhiszemű futtatását írja le ezen a grafikonon, és így van mód arra, hogy az algoritmust ebbe a nyomba illesszük. Az élek típusai elég egyértelműen vannak leírva a Wikipédiában, és ezt a példát is megtekintheti.
- Tudomásul veszem, hogy ez a DFS végrehajtásának érvényes módja. Egyszerűen azt kérdezem, mi lenne, ha másképp csinálnák.
- Akkor az eredmények eltérőek lennének. ‘ sajnálom, ‘ neked magadnak kell megoldanod.
- @soandos Általában ott nagyon jól lehet több DFS bejárás. Az itt használt fogalmak viszonyulnak az adott bejáráshoz, és többszörös áthaladás esetén különböznek egymástól.
Válasz
A DFS átirányítása irányítatlan gráfban nem hagy keresztmetszetet, mivel minden csúcsra eső él feltárásra kerül.
Azonban egy irányított gráfban találkozhat egy élrel ami egy olyan csúcshoz vezet, amelyet korábban felfedeztek, hogy ez a csúcs nem az aktuális csúcs őse vagy leszármazottja. Egy ilyen élt keresztnek nevezünk.
Megjegyzések
- Aporov, köszönöm a választ. Számomra továbbra is úgy tűnik, hogy amikor a DFS-ben a 6-os csúcsra jutunk, amint azt a Wikipédia ábrázolja, akkor három élt kell átmenni 6-tól. Ekkor a 6-os csúcs ” áram “. Végül átmész az élen a 3. csúcsig. Míg a 3 már meglátogatott, annak ellenére, hogy van egy él 6-tól 3-ig, akkor 3 az ” áram leszármazottja. ” 6. csúcs. Ha ez így van, akkor az megsérti a keresztszél definícióját. Valaminek többnek kell lennie a definícióban, amelyet nem ‘ t nagyon egyértelművé tesznek.
- Valójában a DFS csak a hátsó élek egyik fa szélét tartalmazza (Intro Thm. Algoritmusok 22.10).
Válasz
Egy DFS-bejárás során a csomópontok befejeződnek, amint az összes gyermekük megvan. befejezett. Ha bejárása során megjelöli az egyes csomópontok felfedezési és befejezési idejét, akkor a kezdési és befejezési idők összehasonlításával ellenőrizheti, hogy egy csomópont leszármazottja-e. Valójában bármely DFS bejárás felosztja az éleit a következő szabály szerint.
Legyen d [csomópont] a csomópont felfedezésének ideje, ugyanúgy legyen f [csomópont] a befejezés ideje.
Zárójeles tétel Az összes u, v esetében pontosan az alábbiak egyike érvényes:
1.d [u] < f [u] < d [v] < f [ v] vagy d [v] < f [v] < d [u] < f [u], és u és v egyik sem a másik leszármazottja.
d [u] < d [v] < f [v] < f [u] és v u leszármazottja.
d [v] < d [u] < f [u] < f [v] és u a v leszármazottja.
Tehát, d [u] < d [v] < f [u] < f [v] nem történhet.
Tetszik zárójelek: () [], ([]) és [()] rendben vannak, de a [[]] és [(]) nincsenek rendben.
Vegyük például az élekkel ellátott grafikont:
A -> B
A -> C
B -> C
Legyen a látogatás sorrendje: a csomópontok címkéinek húrja, ahol az “ABCCBA” jelentése A -> B -> C (kész) B (kész) A (kész) A (kész), hasonló a ((())) -hez.
Tehát az “ACCBBA” lehet a “(() ())” modellje.
Példák:
“CCABBA”: Ekkor A -> C kereszt él, mivel a CC nincs az A belsejében.
“ABCCBA”: Ekkor A -> C egy elülső él (közvetett leszármazott).
“ACCBBA”: Ekkor A -> C egy fa szél (közvetlen leszármazott).
Források:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Lecure Notes http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm