BFS vs DFS visualiseerija

Vaata, kuidas BFS ja DFS läbivad sama graafi erinevalt. BFS liigub laiuti, DFS liigub sügavuti.

Algväärtused — BFS vs DFS visualiseerija

Graafi eelseadistus	4×4 võrgustik
Alguspunkt	0

Muuda ülal mõnda juhtelementi ja tulemused arvutatakse uuesti.

Interaktiivse simulatsiooni laadimine...

BFS leiab lühima tee ainult siis, kui kõik servad on ühehinnalised 🖖

Tavaline põhjus BFS-i valida on see, et ta annab lühima tee. See garantii on kitsam, kui kõlab: see kehtib, sest BFS käsitleb iga serva ühe sammuna, nii et tippu esimest korda jõudes on ta sinna pääsenud võimalikult väheste hüpetega. Lisa tegelikud kulud — teepikkused, ümberistumistasud, latents — ja garantii haihtub. BFS vastab endiselt enesekindlalt ja vastab valesti, sest kahe kalli servaga tee võib hõlpsasti maksta rohkem kui viie odava servaga tee. Dijkstra algoritm on parandus ja see on peaaegu täpselt järgmine: BFS, kus lihtne järjekord on asendatud prioriteetjärjekorraga.

Sama kaart, kaks reisimisviisi 🖖

Kui käivitada mõlemad kõrvuti, hakkab midagi silma: nad külastavad täpselt samu tippe ja servi, ainult erinevas järjekorras. Laiuti otsing (BFS) uurib enne edasiminekut läbi kogu praeguse naabruskonna ja peab seetõttu meeles pidama iga tippu, mis ootab piiril. Sügavuti otsing (DFS) pühendub ühele harule ja jälgib vaid parajasti käidavat teed. Praktiline järeldus: vali BFS, kui vastus on tõenäoliselt lähedal, ja DFS, kui graaf on sügav ja tahad hoida mälukasutust väiksena.

Mõlemad algoritmid sündisid labürintides 🖖

Ammu enne arvuteid oli sügavuti otsing olemas labürindi läbimise reeglina, mille avaldas prantsuse matemaatik Charles Pierre Trémaux 1800. aastatel. Laiuti otsing jõudis kohale palju hiljem: Edward F. Moore leiutas selle uuesti 1959. aasta artiklis pealkirjaga The Shortest Path Through a Maze, ning Konrad Zuse oli selle juba 1945. aastal visandanud. Kaks arvutiteaduse nurgakivi, mõlemad algselt välja mõeldud lihtsalt selleks, et labürindist välja pääseda.

GRAAFI LÄBIMINE — MILLIST JÄRJEKORDA VAJATE JA MIS SEE MAKSAB?

Millise läbimisjuhtumiga on tegemist?

BFS ja DFS külastavad samu tippe ning erinevad ühe koodirea poolest: järjekord pinu asemel. Kõik ülejäänu tuleneb sellest. Järjekord levib ringidena, nii et esimest korda tippu jõudes on BFS tulnud kõige vähemate servadega teed pidi. Pinu sukeldub, nii et DFS jõuab kaugesse otsa varem, aga mitte ühtegi kindlat teed pidi. Kumba vajate, sõltub küsimusest — ja graafi kujust, mis otsustab, mis kummagi hinnaks on.

Vajate kõige vähem servi — BFS, sest ta külastab kauguskihtide kaupa FIFO ⇒ min |E|

Puu — tasemejärjestus vastu eesjärjestust, ja mälukulu pöördub ümber BFS: O(w), DFS: O(d)

Ahel — mõlemad järjestused langevad kokku ja valik kaotab tähtsuse deg ≤ 2 ⇒ BFS = DFS

Kõik ei ole kättesaadav — ühest alustustipust ei piisa c(G) > 1

Vajate kõige vähem servi — BFS, sest ta külastab kauguskihtide kaupa

Mida te teate: Kaaludeta graaf ja lühima tee küsimus. BFS külastab kõigepealt kõike kaugusel 1, siis kõike kaugusel 2, nii et esimene jõudmine tippu käib mööda lühimat teed.

Reegel: FIFO ⇒ min |E|

Näidisarvutus: 4×4 ruudustikus tipust 0 külastab BFS 0, 1, 4, 2, 5, 8, 3, 6, 9, 12, … — diagonaalne lainefront. DFS külastab 0, 1, 2, 3, 7, 6, 5, 4, … ja jõuab tippu 4 alles kaheksandal sammul.

Ava see juhtum: 4×4 võrgustik

Vajate kõige vähem servi — BFS, sest ta külastab kauguskihtide kaupa. BFS pühib väljapoole kauguskihtide kaupa; DFS looklev tee laskub esmalt ühte koridori. Kaaludeta graaf ja lühima tee küsimus. BFS külastab kõigepealt kõike kaugusel 1, siis kõike kaugusel 2, nii et esimene jõudmine tippu käib mööda lühimat teed. — BFS pühib väljapoole kauguskihtide kaupa; DFS looklev tee laskub esmalt ühte koridori.

Puu — tasemejärjestus vastu eesjärjestust, ja mälukulu pöördub ümber

Mida te teate: Puus on mõlemal järjestusel nimi: BFS on tasemejärjestus, DFS on eesjärjestus. Mõlemad külastavad kõiki 15 tippu; erineb see, kui palju tuleb korraga meeles pidada.

Reegel: BFS: O(w), DFS: O(d)

Näidisarvutus: BFS annab 0, 1, 2, 3, …, 14 — tase tasemelt. DFS annab 0, 1, 3, 7, 8, 4, 9, 10, 2, … — kõigepealt mööda vasakut selgroogu alla. Järjekorra tipp 8, pinu tipp 4.

Ava see juhtum: Binaarpuu

Puu — tasemejärjestus vastu eesjärjestust, ja mälukulu pöördub ümber. Tasemejärjestus täidab iga rea enne allaminekut; eesjärjestus jookseb leheni ja tuleb tagasi. Puus on mõlemal järjestusel nimi: BFS on tasemejärjestus, DFS on eesjärjestus. Mõlemad külastavad kõiki 15 tippu; erineb see, kui palju tuleb korraga meeles pidada. — Tasemejärjestus täidab iga rea enne allaminekut; eesjärjestus jookseb leheni ja tuleb tagasi.

Ahel — mõlemad järjestused langevad kokku ja valik kaotab tähtsuse

Mida te teate: Igal tipul on täpselt üks külastamata naaber, seega on edasi vaid üks tee. BFS ja DFS annavad sama jada ning hoiavad korraga üht tippu.

Reegel: deg ≤ 2 ⇒ BFS = DFS

Näidisarvutus: 12 tipuga ahelas külastavad mõlemad 0, 1, 2, …, 11 selles järjekorras ja mõlema front püsib algusest lõpuni suuruses 1.

Ava see juhtum: Pikk ahel

Ahel — mõlemad järjestused langevad kokku ja valik kaotab tähtsuse. Kui hargneda pole kuhugi, käivad mõlemad läbimised sama joont mööda samas järjekorras. Igal tipul on täpselt üks külastamata naaber, seega on edasi vaid üks tee. BFS ja DFS annavad sama jada ning hoiavad korraga üht tippu. — Kui hargneda pole kuhugi, käivad mõlemad läbimised sama joont mööda samas järjekorras.

Kõik ei ole kättesaadav — ühest alustustipust ei piisa

Mida te teate: Graaf on tükkideks jagunenud. Ühest tipust alustades külastab kumbki läbimine ainult seda komponenti, kuhu see tipp kuulub, ja jääb siis seisma.

Reegel: c(G) > 1

Näidisarvutus: Kümne tipuga graafi tipust 0 külastavad nii BFS kui ka DFS täpselt 4 tippu ja peatuvad. Tippe 4, 5, 6, 7, 8 ja 9 ei puudutata kunagi.

Ava see juhtum: Ühendamata

Kõik ei ole kättesaadav — ühest alustustipust ei piisa. Neli tippu kättesaadavad, kuus mitte: üks algus uurib läbi ühe komponendi ja rohkem mitte. Graaf on tükkideks jagunenud. Ühest tipust alustades külastab kumbki läbimine ainult seda komponenti, kuhu see tipp kuulub, ja jääb siis seisma. — Neli tippu kättesaadavad, kuus mitte: üks algus uurib läbi ühe komponendi ja rohkem mitte.

Allikad (2)

Insight block 3 — BFS as a maze algorithm: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.
Trémaux's rule, as it was actually published: É. Lucas, Récréations mathématiques, vol. 1. Gauthier-Villars, Paris, 1882 — Lucas credits the maze-walking procedure to Charles Pierre Trémaux.

Ülesanne täielikult lahendatud

16 sõlme ja 16 servaga labürindi läbimine 5 sammu
Labürindis on 16 tippu, mida ühendab 16 serva. Arvutage, mitme tipuni jõuab tipust 0 algav läbimine ja kui kaugel on tipp 15 tipust 0. See on olek Labürindi koridor algtipuga 0.
1. Kirjutage labürint enne mis tahes muud tegevust üles naabrusnimekirjana. Tipp 4 on see, mida tasub tähele panna: seda ei puuduta mitte ükski serv, seega on selle aste 0 ja ükski mujalt algav läbimine ei jõua kunagi selleni.
  
  $0 : 11 : 0, 2, 52 : 1, 33 : 24 : \emptyset 5 : 1, 6, 96 : 5, 7, 107 : 6, 118 : 9, 12 9 : 5, 8, 1010 : 6, 9, 1411 : 7, 15 12 : 8, 1313 : 12, 1414 : 10, 1315 : 11$
2. Laiusotsing sorteerib kättesaadava kihtidesse, kusjuures kiht k koosneb kõigest sellest, mida kohtatakse esimest korda kihist k − 1. Nende moodustamine on pigem sulund kui teekond — kiht viiakse täielikult lõpule enne järgmise avamist ja ükski tipp ei esine kaks korda.
  
  $L_{0} L_{3} L_{6} = {0} = {3, 6, 9} = {13, 15} L_{1} L_{4} = {1} = {7, 8, 10} L_{2} L_{5} = {2, 5} = {11, 12, 14}$
3. Liitke kihtide suurused. Läbimine jõuab 15 tipuni, mis on ühe võrra vähem kui graafis sisalduvad 16, ja seepärast peatub sammuloendur ühe võrra allpool tippude arvu.
  
  $1 + 1 + 2 + 3 + 3 + 3 + 2 = 15, n = 16, de g (4) = 0$
4. Tipp 15 ilmub esimest korda kihis 6 ja kihi number on kaugus: tipp pannakse järjekorda vaid sellest ülalpool asuva kihi tipust, seega ei jõuta millenigi kihis 6 vähema kui 6 servaga. Marsruut 0-1-5-6-7-11-15 saavutab 6, seega on tõke täpne.
  
  $15 \in L_{6} ⟹ d (0, 15) = 6 : 0 \to 1 \to 5 \to 6 \to 7 \to 11 \to 15$
5. Sügavuti otsingul sellist invarianti pole. Kui läbija valib tipus 1 enne tipu 2 tippu 5, seejärel tipus 5 enne tipu 6 tippu 9 ning tipus 9 enne tipu 10 tippu 8, on iga valik külastamata naabrite seast lubatud. Nii suundub ta mööda pikka koridori ja pöördub tagasi alles siis, kui enam edasi minna ei saa. Tippu 15 jõuab ta 12 servast koosneva tee kaugeimas otsas ning see tee on saavutatavuse küsimusele täiesti korrektne vastus.
  
  $0 \to 1 \to 5 \to 9 \to 8 \to 12 \to 13 \to 14 \to 10 \to 6 \to 7 \to 11 \to 15 ⟹ ℓ = 12$
Vastus

Tipp 15 asub algusest 6 serva kaugusel ja sügavusotsingu teekond võib anda samasse kohta 12-servalise marsruudi. Kordaja 2 ei ole põnev osa; huvitav on see, kust otsetee üldse tulla saab. Kättesaadav komponent sisaldab 15 tippu, seega kasutab selle mis tahes toespuu 14 serva — ja labürindis on 16 serva, mis tähendab, et täpselt 2 serva on üleliigsed. Kustutage need 2 ja järelejäänu on puu, kus mis tahes tipupaari vahel on täpselt üks tee, nii et kaks paneeli nõustuksid siis iga kaugusega ja erineksid vaid läbimise järjekorra poolest. Iga lahkarvamus nende vahelise kauguse osas taandub nendele 2 lisaservale. See on ka põhjus, miks sügavusotsing on odavam harjumus, kui küsimus on vaid selles, kas tipp on kättesaadav, ja vale valik hetkest, kui küsimuseks saab, kui kaugel.

$∣ E ∣ - (∣ V ∣ - 1) = 16 - (15 - 1) = 2$

42Mathi meeskond · Uuendatud 2026-07-27

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

4×4 võrgustik - 4×4 võrgustik: BFS uurib kihthaaval
Labürindikäik - Labürindikoridor
Tähtgraaf - Üheksa kodarat, iga tipp keskusest ühe sammu kaugusel. Sügavusotsingul pole kuhugi süvitsi minna ja nii tagastabki see laiusotsinguga täpselt sama järjestuse.
Pikk ahel - Kaksteist tippu reas. Järjestused on taas identsed. Tähtgraafi üheksa tipu asemel hoiab iga algoritm siin korraga mälus vaid üht.
Binaarpuu - Binaarpuu: DFS liigub enne sügavuti kui laiuti
Ühendamata - Kaks ruutu ja kaks isoleeritud tippu. Tipust 0 algav läbimine jõuab 10 tipust 4-ni. Ka kõige põhjalikum otsing ei suuda ülejäänuid leida.
Tihe graaf - Tihe graaf: palju servi, sarnased läbimisjärjekorrad