Ennen kuin tarkastelemme BFS:n ja DFS:n eroja, meidän pitäisi ensin tietää BFS:stä ja DFS:stä erikseen.

Mikä on BFS?

BFS tarkoittaa Leveys ensimmäinen haku . Se tunnetaan myös nimellä tason tilauksen läpikulku . Queue-tietorakennetta käytetään Breadth First -haun läpikäymiseen. Kun käytämme BFS-algoritmia graafin läpikulkuun, voimme pitää mitä tahansa solmua juurisolmuna.

Tarkastellaan alla olevaa kaaviota leveyden ensimmäisen haun läpikäymisestä.

merkkijonotaulukon luominen javassa

Oletetaan, että pidämme solmua 0 juurisolmuna. Siksi kulku aloitettaisiin solmusta 0.

Kun solmu 0 poistetaan jonosta, se tulostetaan ja merkitään a vieraili solmussa.

Kun solmu 0 poistetaan jonosta, solmun 0 viereiset solmut lisätään jonoon alla olevan kuvan mukaisesti:

Nyt solmu 1 poistetaan jonosta; se tulostetaan ja merkitään vierailluksi solmuksi

Kun solmu 1 poistetaan jonosta, kaikki solmun 1 viereiset solmut lisätään jonoon. Solmun 1 viereiset solmut ovat 0, 3, 2, 6 ja 5. Mutta meidän täytyy lisätä vain vierailemattomia solmuja jonoon. Koska solmut 3, 2, 6 ja 5 ovat vierailemattomia; siksi nämä solmut lisätään jonoon alla olevan kuvan mukaisesti:

Seuraava solmu on 3 jonossa. Joten solmu 3 poistetaan jonosta, se tulostetaan ja merkitään käydyksi alla olevan kuvan mukaisesti:

Kun solmu 3 poistetaan jonosta, kaikki solmun 3 viereiset solmut, lukuun ottamatta vierailtuja solmuja, lisätään jonoon. Solmun 3 viereiset solmut ovat 0, 1, 2 ja 4. Koska solmuissa 0, 1 on jo vierailtu ja solmu 2 on jonossa; siksi meidän täytyy lisätä vain solmu 4 jonoon.

powershell pienempi tai yhtä suuri kuin

Nyt jonon seuraava solmu on 2. Joten 2 poistettaisiin jonosta. Se tulostetaan ja merkitään käydyksi alla olevan kuvan mukaisesti:

Kun solmu 2 poistetaan jonosta, kaikki solmun 2 viereiset solmut vierailtuja solmuja lukuun ottamatta lisätään jonoon. Solmun 2 viereiset solmut ovat 1, 3, 5, 6 ja 4. Koska solmuissa 1 ja 3 on jo vierailtu ja 4, 5, 6 on jo lisätty jonoon; siksi meidän ei tarvitse lisätä mitään solmua jonoon.

Seuraava elementti on 5. Joten 5 poistettaisiin jonosta. Se tulostetaan ja merkitään käydyksi alla olevan kuvan mukaisesti:

Kun solmu 5 poistetaan jonosta, jonoon lisätään kaikki solmun 5 viereiset solmut vierailtuja solmuja lukuun ottamatta. Solmun 5 viereiset solmut ovat 1 ja 2. Koska molemmissa solmuissa on jo vierailtu; siksi jonoon ei ole lisättävää kärkeä.

Seuraava solmu on 6. Joten 6 poistettaisiin jonosta. Se tulostetaan ja merkitään käydyksi alla olevan kuvan mukaisesti:

Kun solmu 6 poistetaan jonosta, jonoon lisätään kaikki solmun 6 viereiset solmut vierailtuja solmuja lukuun ottamatta. Solmun 6 viereiset solmut ovat 1 ja 4. Koska solmussa 1 on jo vierailtu ja solmu 4 on jo lisätty jonoon; siksi jonoon ei ole lisättävää kärkeä.

manuaalinen testaus

Seuraava elementti jonossa on 4. Eli 4 poistettaisiin jonosta. Se tulostetaan ja merkitään käydyksi.

Kun solmu 4 poistetaan jonosta, jonoon lisätään kaikki solmun 4 viereiset solmut vierailtuja solmuja lukuun ottamatta. Solmun 4 viereiset solmut ovat 3, 2 ja 6. Koska kaikissa vierekkäisissä solmuissa on jo vierailtu; joten jonoon ei ole lisättävää kärkeä.

Mikä on DFS?

DFS tarkoittaa Depth First Search. DFS traversalissa käytetään pinotietorakennetta, joka toimii LIFO-periaatteella (Last In First Out). DFS:ssä läpikulku voidaan aloittaa mistä tahansa solmusta tai voidaan sanoa, että mitä tahansa solmua voidaan pitää juurisolmuna, kunnes juurisolmua ei mainita ongelmassa.

BFS:n tapauksessa jonosta poistettava elementti, poistetun solmun viereiset solmut lisätään jonoon. Sitä vastoin DFS:ssä pinosta poistetaan elementti, jonka jälkeen pinoon lisätään vain yksi viereinen poistetun solmun solmu.

Tarkastellaan alla olevaa kaaviota Syvyys ensimmäinen haku -läpikulkua varten.

Harkitse solmua 0 juurisolmuna.

Ensin lisäämme elementin 0 pinoon alla olevan kuvan mukaisesti:

Solmussa 0 on kaksi vierekkäistä solmua, eli 1 ja 3. Nyt voimme ottaa vain yhden vierekkäisen solmun, joko 1 tai 3, kulkemaan. Oletetaan, että tarkastelemme solmua 1; siksi 1 lisätään pinoon ja tulostetaan alla olevan kuvan mukaisesti:

Nyt tarkastellaan solmun 1 vierekkäisiä pisteitä. Solmun 1 vierailemattomat vierekkäiset pisteet ovat 3, 2, 5 ja 6. Voimme tarkastella mitä tahansa näistä neljästä kärjestä. Oletetaan, että otamme solmun 3 ja lisäämme sen pinoon alla olevan kuvan mukaisesti:

Tarkastellaan solmun 3 vierailemattomia vierekkäisiä pisteitä. Solmun 3 vierailemattomat vierekkäiset kärjet ovat 2 ja 4. Voimme ottaa jommankumman pisteistä, eli 2 tai 4. Oletetaan, että otamme pisteen 2 ja lisäämme sen pinoon alla olevan kuvan mukaisesti:

komento chown

Solmun 2 vierailemattomat vierekkäiset kärjet ovat 5 ja 4. Voimme valita jommankumman pisteistä, eli 5 tai 4. Oletetaan, että otamme kärkipisteen 4 ja lisäämme pinoon alla olevan kuvan mukaisesti:

Nyt tarkastellaan solmun 4 vierailemattomia vierekkäisiä kärkipisteitä. Solmun 4 vierailematon viereinen kärkipiste on solmu 6. Siksi elementti 6 lisätään pinoon alla esitetyllä tavalla:

Kun elementti 6 on lisätty pinoon, tarkastellaan solmun 6 vierekkäisiä pisteitä, joita ei ole vierailtu. Koska solmun 6 vierekkäisiä pisteitä ei ole vierailtuja, emme voi siirtyä solmun 6 ulkopuolelle. Tässä tapauksessa suoritamme perääntymistä . Ylin elementti, eli 6, ponnattaisiin ulos pinosta alla olevan kuvan mukaisesti:

Pinon ylin elementti on 4. Koska solmusta 4 ei ole vierekkäisiä vierekkäisiä pisteitä; siksi solmu 4 ponnahtaa ulos pinosta alla olevan kuvan mukaisesti:

Pinon seuraava ylin elementti on 2. Nyt tarkastellaan solmun 2 vierekkäisiä solmupisteitä, joissa ei ole vierailtu. Koska vain yksi vierailematon solmu eli 5 on jäljellä, solmu 5 työnnetään pinoon 2:n yläpuolella ja tulostetaan kuten alla:

Nyt tarkastetaan solmun 5 viereiset kärjet, jotka ovat vielä vierailemattomia. Koska vierailevaa kärkeä ei ole jäljellä, ponnaamme elementin 5 pinosta alla olevan kuvan mukaisesti:

Emme voi siirtyä viittä pidemmälle, joten meidän on suoritettava taaksepäin. Perääntymisessä ylin elementti ponnahtaa ulos pinosta. Ylin elementti on 5, joka ponnahtaa ulos pinosta, ja siirrymme takaisin solmuun 2 alla olevan kuvan mukaisesti:

Nyt tarkastetaan solmun 2 viereiset vierekkäiset kärjet. Koska vierekkäistä kärkeä ei ole jäljellä vierailla, suoritamme paluumatkan. Paluumatkassa ylin elementti, eli 2, ponnattaisiin ulos pinosta ja siirrytään takaisin solmuun 3 alla olevan kuvan mukaisesti:

Nyt tarkastetaan solmun 3 viereiset vierekkäiset kärjet. Koska vierekkäistä kärkeä ei ole jäljellä vierailla, suoritamme paluumatkan. Paluumatkassa ylin elementti, eli 3, ponnahtaa ulos pinosta ja siirrytään takaisin solmuun 1 alla olevan kuvan mukaisesti:

linux kuinka nimetä hakemisto uudelleen

Kun elementti 3 on ponnahtanut esiin, tarkistamme solmun 1 viereiset vierekkäiset kärjet. Koska vierailevaa kärkeä ei ole jäljellä; siksi paluumatka suoritetaan. Paluumatkassa ylin elementti, eli 1, ponnattaisiin ulos pinosta ja siirrytään takaisin solmuun 0 alla olevan kuvan mukaisesti:

Tarkistamme solmun 0 viereiset kärjet, jotka ovat vielä vierailemattomia. Koska vierekkäistä huippupistettä ei ole jäljellä vierailla, suoritamme paluumatkan. Tässä vain yksi elementti, eli 0, joka on jäljellä pinossa, ponnahtaa ulos pinosta alla olevan kuvan mukaisesti:

Kuten yllä olevasta kuvasta voidaan havaita, pino on tyhjä. Joten meidän on lopetettava DFS-läpikulku tässä, ja tulostetut elementit ovat tulosta DFS-läpikulusta.

Erot BFS:n ja DFS:n välillä

Seuraavat ovat erot BFS:n ja DFS:n välillä: