BFS ir DFS

Video.: 5.1 Graph Traversals - BFS & DFS -Breadth First Search and Depth First Search

Turinys

Turinys: skirtumas tarp BFS ir DFS
Palyginimo diagrama
BFS
DFS
Pagrindiniai skirtumai
Išvada
Aiškinamasis vaizdo įrašas

Skirtumas tarp BFS, tai yra paieška iš pirmo pločio, ir DFS, kuri yra paieška iš pirmo gylio, yra tai, kad pirmo pločio paieška yra grafiko judėjimo metodas, kuriame naudojama eilė lankomoms viršūnėms laikyti, o pirmoji gylis - grafikas, einantis metodu, kuris naudoja krūvą. skirtas aplankytoms viršūnėms laikyti.

Pirmoji įkvėpimo ir pirmo gylio paieška yra viena iš svarbiausių sąvokų kompiuteriniame programavime. Pirma gylio paieška eina keliu nuo pradžios iki pabaigos, tai yra pabaigos mazgas, kita vertus, duonos pirmoji paieška darbo lygiu. Jei kalbėsime apie pagrindinį skirtumą, tada pagrindinis skirtumas tarp BFS, kuris yra pirmoji plotis, ir DFS, ty pirmoji gylis, yra ta, kad pirmoji plotis paieška yra grafikas, einantis metodas, kuriame naudojama eilė aplankytų viršūnių saugojimui, o gylio pirmoji paieška yra grafiko perėjimo metodas, kuris naudoja krūvą aplankytų viršūnių saugojimui. Pirma platumo paieška, kuri trumpai vadinama BFS, BFS naudojama norint pereiti grafiką. Eilė naudojama aplankytų viršūnių saugojimui BFS. BFS dirba su viršūnėmis, aplankytos viršūnės saugomos eilėje. Viršūnės saugomos viena po kitos. Kiekvienas grafiko mazgas yra visiškai ištirtas ir aplankytos kitos grafiko viršūnės.

Gylis Pirmoji paieška, vadinama DFS, taip pat yra grafiko perėjimo metodas, kuris naudojo krūvą viršūnėms saugoti. Pirmojo pločio paieška nėra metodas, paremtas briauna, o pirmojo gylio paieška yra kraštinė. Pirmasis gylis ieškomas rekursyviuoju būdu, kai viršūnės tiriamos per kraštus. Išsamiai atlikus pirmą paiešką, kiekviena viršūnė aplanko vieną kartą ir apžiūrima du kartus.

Turinys: skirtumas tarp BFS ir DFS

Palyginimo diagrama
BFS
DFS
Pagrindiniai skirtumai
Išvada
Aiškinamasis vaizdo įrašas

Palyginimo diagrama

Pagrindas	BFS	DFS
Reikšmė	Pirmoji platumos paieška yra grafiko perėjimo metodas, kuriame naudojama eilė lankomoms viršūnėms laikyti	Pirma gylio paieška yra grafiko perėjimo metodas, kuris naudoja krūvą aplankytų viršūnių saugojimui.
Algoritmas	Pirma platiausia paieška yra pagrįsta viršūnių algoritmu	Pirmoji gylis yra briaunomis pagrįstas algoritmas
Atmintis	Pirma platiausia paieška yra neveiksminga atmintis	Pirma gylio paieška yra efektyvi atmintis
Taikymas	Tiriamas dvipusis grafikas, prijungtas komponentas ir trumpiausias grafike esantis kelias.	Nagrinėja dviejų kraštų sujungtą grafiką, stipriai sujungtą grafiką, aciklinį grafiką ir topologinę tvarką.

BFS

Pirma platumo paieška, kuri trumpai vadinama BFS, BFS naudojama norint pereiti grafiką. Eilė naudojama aplankytų viršūnių saugojimui BFS. BFS dirba su viršūnėmis, aplankytos viršūnės saugomos eilėje. Viršūnės saugomos viena po kitos. Kiekvienas grafiko mazgas yra visiškai ištirtas, o tada aplankytos kitos grafiko viršūnės. Pirma pločio paieška naudojama norint sužinoti, ar grafikas yra prijungtas, ar ne. Dviejų dalių grafikui aptikti naudojama pirmoji platuma. Trumpiausi keliai nustatomi naudojant BFS.

DFS

Gylis Pirmoji paieška, vadinama DFS, taip pat yra grafiko perėjimo metodas, kuris naudojo krūvą viršūnėms saugoti. Pirmojo pločio paieška nėra metodas, paremtas briauna, o pirmojo gylio paieška yra kraštinė.Pirmasis gylis ieškomas rekursyviuoju būdu, kai viršūnės tiriamos per kraštus. Atlikus pirmąjį gylį, kiekviena viršūnė aplanko vieną kartą, apžiūrint du kartus.

Pagrindiniai skirtumai

Pirma pločio paieška yra grafiko judėjimo metodas, kuriame naudojama eilė lankomoms viršūnėms laikyti, tuo tarpu „gylis pagal pirmąjį“ yra grafiko judėjimo metodas, kuris naudoja krūvą aplankytų viršūnių saugojimui.
Pirmojo pločio paieška yra algoritmas, paremtas viršūnėmis, o pirmasis gylis - kraštinis algoritmas
Pirmojo pločio paieška yra neveiksminga atmintyje, tuo tarpu pirmo gylio paieška yra efektyvi atmintyje.
Tiria dvipusį grafiką, sujungtą komponentą ir trumpiausią grafike esantį kelią, tuo tarpu tiria dviejų kraštų sujungtą grafiką, stipriai sujungtą grafiką, aciklinį grafiką ir topologinę tvarką.