BFS vs. DFS
Obsah
Rozdiel medzi BFS, ktorým je vyhľadávanie na prvom mieste a DFS, ktoré je na prvom mieste, je ten, že vyhľadávanie na prvom mieste je metóda prechodu grafom, ktorá používa front na ukladanie navštívených vrcholov, zatiaľ čo vyhľadávanie na prvom mieste je metóda prechodu cez graf, ktorá využíva balík na ukladanie navštívených vrcholov.
Dychové a hĺbkové vyhľadávanie sú jedným z najdôležitejších konceptov počítačového programovania. Hĺbkové vyhľadávanie sleduje cestu od začiatku do konca, ktorá je koncovým uzlom, na druhej strane, prvá pracovná úroveň prvého hľadania je na úrovni. Ak hovoríme o hlavnom rozdiele, potom hlavným rozdielom medzi BFS, ktorým je prvé vyhľadávanie v šírke a DFS, ktoré je hĺbkovým prvým vyhľadávaním, je to, že prvé vyhľadávanie v šírke je metóda prechodu grafom, ktorá používa front na ukladanie navštívených vrcholov, zatiaľ čo vyhľadávanie v hĺbke ako prvé je metóda posuvu grafov, ktorá používa zásobník na ukladanie navštívených vrcholov. Prvé šírkové vyhľadávanie, ktoré sa nazýva krátko BFS, sa používa na prechádzanie grafom. Fronta sa používa na ukladanie navštívených vrcholov v BFS. BFS pracujú na vrcholoch, navštívené vrcholy sa ukladajú do frontu. Vrcholy sa ukladajú jeden po druhom. Každý uzol v grafe je úplne preskúmaný a potom sú navštívené ďalšie vrcholy grafu.
Hĺbka Prvé vyhľadávanie, ktoré sa nazýva DFS, je tiež metóda prechodu grafom, ktorá používa zásobník na ukladanie vrcholov. Vyhľadávanie podľa šírky nie je metóda založená na okraji, zatiaľ čo vyhľadávanie na hĺbke je metóda založená na okraji. Hĺbkové vyhľadávanie sa vykonáva rekurzívnym spôsobom, pri ktorom sa vrcholy skúmajú hranami. Pri prvom hĺbkovom vyhľadávaní sa každý vrchol navštívi raz a potom dvakrát.
Obsah: Rozdiel medzi BFS a DFS
- Porovnávacia tabuľka
- BFS
- DFS
- Kľúčové rozdiely
- záver
- Vysvetľujúce video
Porovnávacia tabuľka
| základ | BFS | DFS |
| zmysel | Prvé vyhľadávanie v šírke je metóda prechádzania grafom, ktorá používa front na ukladanie navštívených vrcholov | Hĺbkovým vyhľadávaním je metóda prechodu grafom, ktorá používa zásobník na ukladanie navštívených vrcholov. |
| algoritmus | Prvé vyhľadávanie šírky je algoritmus založený na vrchole | Hĺbkové vyhľadávanie je algoritmus založený na okraji |
| Pamäť | Prvé vyhľadávanie v šírke je neefektívne | Hĺbkové vyhľadávanie je efektívne z hľadiska pamäte |
| prihláška | Skúma bipartitný graf, pripojený komponent a najkratšiu cestu prítomnú v grafe. | Skúma dva hrany pripojený graf, silne pripojený graf, acyklický graf a topologické poradie. |
BFS
Prvé šírky vyhľadávania, ktoré sa nazývajú krátko BFS, sa používajú na prechádzanie grafom. Fronta sa používa na ukladanie navštívených vrcholov v BFS. BFS pracujú na vrcholoch, navštívené vrcholy sa ukladajú do frontu. Vrcholy sa ukladajú jeden po druhom. Každý uzol v grafe je úplne preskúmaný a potom sú navštívené ďalšie vrcholy grafu. Vyhľadávanie podľa šírky sa používa na zistenie, či je graf prepojený alebo nie. Šírka prvého vyhľadávania sa používa na detekciu bipartitného grafu. Nájdenie najkratších ciest sa uskutoční pomocou BFS.
DFS
Hĺbka Prvé vyhľadávanie, ktoré sa nazýva DFS, je tiež metóda prechodu grafom, ktorá používa zásobník na ukladanie vrcholov. Vyhľadávanie podľa šírky nie je metóda založená na okraji, zatiaľ čo vyhľadávanie na hĺbke je metóda založená na okraji.Hĺbkové vyhľadávanie sa vykonáva rekurzívnym spôsobom, pri ktorom sa vrcholy skúmajú hranami. Pri hĺbkovom vyhľadávaní je každý vrchol navštívený raz, ktorý je skontrolovaný dvakrát.
Kľúčové rozdiely
- Prvé vyhľadávanie v šírke je metóda prechádzania grafom, ktorá používa front na ukladanie navštívených vrcholov, zatiaľ čo vyhľadávanie v hĺbke je metóda prechádzania grafom, ktorá používa zásobník na ukladanie navštívených vrcholov.
- Vyhľadávanie v šírke - prvý je algoritmus založený na vrchole, zatiaľ čo vyhľadávanie na hĺbku - prvý je algoritmus na okraji
- Vyhľadávanie v prvom šírke je neefektívne, zatiaľ čo vyhľadávanie v prvom rade je efektívne v pamäti.
- Skúma bipartitný graf, pripojený komponent a najkratšiu cestu prítomnú v grafe, zatiaľ čo skúma graf s dvoma hranami, silne pripojený graf, acyklický graf a topologické poradie.
záver
V tomto článku vyššie vidíme jasný rozdiel medzi prvým dychom a hĺbkovým prieskumom pri implementácii.
