Ensimmäisessä syvyydessä olevassa puussa reunat määrittävät puun (ts. Reunat, joita käytettiin kulkua).
Joitakin jäljellä olevia reunoja yhdistää joitain muita solmuja. Mitä eroa on ristireunalla ja etureunalla?
Wikipediasta:
Tämän kattavan puun perusteella reunat Alkuperäisen kuvaaja voidaan jakaa kolmeen luokkaan: etureunat, jotka osoittavat puun solmusta johonkin sen jälkeläisistä, takareunat, jotka osoittavat solmusta yhteen esi-isistään, ja poikittaiset reunat, jotka eivät kumpikaan. Joskus puun reunat eli itse puuhun kuuluvat reunat luokitellaan erillään etureunoista. Jos alkuperäistä kuvaajaa ei ole suunnattu, kaikki sen reunat ovat puun reunoja tai takareunoja.
Ei reunaa, jota ei käytetä liikkeessä. pisteet yhdestä solmusta toiseen muodostavat vanhemman ja lapsen suhteen?
Kommentit
- Liittyvät: cs.stackexchange.com/questions/99988/… pyrkii luomaan algoritmin, joka suuntautuneelle graafille mieluummin tekee eteenpäin reunojen sijasta etureunoja syvyyshaku.
vastaus
Wikipedialla on vastaus:
Kaikkien reunojen tyypit näkyvät tässä kuvassa. Jäljitä DFS tässä kaaviossa (solmut tutkitaan numerojärjestyksessä) ja katso missä intuitio epäonnistuu.
Tämä selittää kaavion: –
Etureuna: (u, v), jossa v on u: n jälkeläinen, mutta ei puun reunaa Se on muu kuin puun reuna joka yhdistää kärjen DFS-puun jälkeläiseen.
Ristireuna: mikä tahansa muu reuna. Voi siirtyä saman syvyyspuun tai eri syvyysluokan puiden pisteiden välillä. (maallikko)
Se on mikä tahansa muu reuna kaaviossa G. Se yhdistää kahden eri DFS-puun tai kahden saman DFS-puun kärjet, joista kumpikaan ei ole toisen esi-isä. (muodollinen)
Kommentit
- Miksi ei ole mahdotonta, että kuusi on ylitetty ensin (oikea puoli ensin)? Jos näin olisi tapahtunut, mitä 2- > 3 -reunaa olisi kutsuttu?
- @soandos, suosittelen, että otat itsellesi aikaa algoritmin jäljittämiseen. Olettaen, että wikipediläiset eivät ole tehneet virhettä ', kuva kuvaa DFS: n rehellistä suoritusta tässä kaaviossa, joten algoritmi on mahdollista sovittaa tähän jälkiin. Reunatyypit on kuvattu riittävän selvästi Wikipediassa, ja voit myös tutustua tähän esimerkkiin.
- Ymmärrän, että tämä on kelvollinen tapa tehdä DFS. Kysyn vain, jos se tehdään toisin.
- Silloin tulokset olisivat erilaiset. Olen ' pahoillani, sinun on ' tehtävä itse.
- @soandos Yleensä siellä voi hyvin olla useita DFS-kulkuja. Tässä käytetyt käsitteet ovat suhteessa annettuun läpikulkuun ja eroavat useissa läpikulkuissa.
Vastaus
DFS-kulku suuntaamattomassa kuvaajassa ei jätä poikittaista reunaa, koska tutkitaan kaikki kärkeen sattuvat reunat.
Suunnatussa kaaviossa saatat kuitenkin törmätä reunaan joka johtaa ennemmin löydettyyn kärkeen, joka ei ole nykyisen kärjen esi-isä tai jälkeläinen. Tällaista reunaa kutsutaan poikittaiseksi reunaksi.
Kommentit
- Aporov, kiitos vastauksesta. Minusta tuntuu silti, että kun pääset DFS: n kärkeen 6 Wikipedian kaaviolla, sinulla on kolme reunaa, jotka on kuljettava 6: sta. Siinä vaiheessa kärki 6 on " nykyinen ". Lopulta aiot kulkea reuna pisteeseen 3. Vaikka 3 on jo käynyt, vaikka reunaa on 6: sta 3: een, niin 3 on " -virran jälkeläinen " kärki 6. Jos näin on, se rikkoo poikkileikkauksen määritelmää. Määritelmässä on oltava jotain muuta, jota ' t ei tehdä kovin yksiselitteiseksi.
- Itse asiassa DFS sisältää vain jommankumman puun reunan takareunoille ( Algoritmit Thm. 22.10).
Vastaus
DFS-solmun solmukohdat ovat valmiit, kun kaikki heidän lapsensa ovat valmis. Jos merkitset jokaisen solmun löytö- ja lopetusajat läpikulun aikana, voit tarkistaa alku- ja lopetusajan vertaamalla, onko solmu jälkeläinen. Itse asiassa mikä tahansa DFS-kulku osaa sen reunat seuraavan säännön mukaisesti.
Olkoon d [solmu] solmun löytöaika, samoin olkoon f [solmu] lopetusaika.
Sulkulause Lauseke kaikille u, v: lle täsmälleen yksi seuraavista:
1.d [u] < f [u] < d [v] < f [ v] tai d [v] < f [v] < d [u] < f [u] eikä kumpikaan u: sta ja v: stä ole toisen jälkeläinen.
d [u] < d [v] < f [v] < f [u] ja v on u: n jälkeläinen.
d [v] < d [u] < f [u] < f [v] ja u on v: n jälkeläinen.
Joten, d [u] < d [v] < f [u] < f [v] ei voi tapahtua.
Kuten sulkeet: () [], ([]) ja [()] ovat kunnossa, mutta ([)] ja [(]) eivät ole kunnossa.
Tarkastellaan esimerkiksi kuvaajia, joissa on reunat:
A -> B
A -> C
B -> C
Olkoon vierailujärjestys edustettuna merkkijono solmuista, joissa ”ABCCBA” tarkoittaa A -> B -> C (valmis) B (valmis) A (valmis), samanlainen kuin ((())).
Joten ”ACCBBA” voi olla malli mallille ”(() ())”.
Esimerkkejä:
”CCABBA”: Tällöin A -> C on risti reuna, koska CC ei ole A: n sisällä.
”ABCCBA”: Tällöin A -> C on etureuna (epäsuora jälkeläinen).
”ACCBBA”: Sitten A -> C on puun reuna (suora jälkeläinen).
Lähteet:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Lecure-muistiinpanot http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm