BFS vs DFS
Sisu
Erinevus BFS-ist, mis on laiusega esimene otsing, ja DFS-ist, mis on sügavusest esimene otsing, on see, et laiuse esimene otsing on graafikut läbitav meetod, mis kasutab järjekorda külastatud tippude salvestamiseks, samal ajal kui esimese sügavuse otsing on graafikut läbiv meetod, mis kasutab virna. külastatud tippude säilitamiseks.
Esimene hingamine ja esimene sügavusotsing on arvutiprogrammeerimises üks olulisemaid mõisteid. Esimene sügavusotsing järgib teed algusest lõpuni, st lõppsõlm, teiselt poolt leiva esimene otsimine töö tasandil. Kui me räägime peamisest erinevusest, siis peamine erinevus BFS-i, st laiuse esimese otsingu ja DFS-i vahel, mis on sügavus-esimene otsing, on see, et laiuse esimene otsing on graafikut läbiv meetod, mis kasutab järjekorda külastatud tippude salvestamiseks, samas kui sügavus-esimene otsing on graafikut läbiv meetod, mis kasutab virna külastatud tippude salvestamiseks. Laiuse esimene otsing, mida nimetatakse lühidalt BFS, kasutatakse graafiku läbimiseks BFS-i. Järjekorda kasutatakse külastatud tippude salvestamiseks BFS-is. BFS töötab tippudel, külastatud tipud salvestatakse järjekorda. Tippe salvestatakse ükshaaval. Graafiku iga sõlme uuritakse täielikult ja seejärel külastatakse graafi teisi tippe.
Sügavus Esimene otsing, mida tuntakse DFS-na, on ka graafikut läbiv meetod, mis kasutas virna tippude salvestamiseks. Laiuse esimene otsing ei ole servapõhine meetod, samas kui esimese sügavuse otsing on servapõhine meetod. Esimene sügavusotsing toimub rekursiivsel viisil, kus tippe uuritakse servade kaudu. Esimese põhjaliku otsingu korral külastatakse igat tippu üks kord, kui seda kontrollitakse kaks korda.
Sisu: erinevus BFSi ja DFSi vahel
- Võrdlusdiagramm
- BFS
- DFS
- Peamised erinevused
- Järeldus
- Selgitav video
Võrdlusdiagramm
| Alus | BFS | DFS |
| Tähendus | Esimene laiuse otsing on graafikut läbiv meetod, mis kasutab külastatud tippude salvestamiseks järjekorda | Esimene sügavusotsing on graafikut läbiv meetod, mis kasutab virna külastatud tippude salvestamiseks. |
| Algoritm | Esimene laiuseotsing on tipupõhine algoritm | Esimene sügavusotsing on servapõhine algoritm |
| Mälu | Esimene laiuseotsing on mälu ebaefektiivne | Esimene sügavusotsing on mälu efektiivne |
| Rakendus | Uurib kahepoolset graafi, ühendatud komponenti ja graafiku lühimat rada. | Uurib kahe servaga ühendatud graafikut, tugevalt ühendatud graafi, atsüklilist graafi ja topoloogilist järjestust. |
BFS
Laiuse esimene otsing, mida nimetatakse lühidalt BFS, kasutatakse graafiku läbimiseks BFS-i. Järjekorda kasutatakse külastatud tippude salvestamiseks BFS-is. BFS töötab tippudel, külastatud tipud salvestatakse järjekorda. Tippe salvestatakse ükshaaval. Graafiku iga sõlme uuritakse täielikult ja seejärel külastatakse graafi teisi tippe. Laiuse järgi otsimist kasutatakse selleks, et leida, kas graaf on ühendatud või mitte. Kahepoolse graafiku tuvastamiseks kasutatakse laiuse esimest otsingut. Lühimate teede leidmiseks kasutatakse BFS-i.
DFS
Sügavus Esimene otsing, mida tuntakse DFS-na, on ka graafikut läbiv meetod, mis kasutas virna tippude salvestamiseks. Laiuse esimene otsing ei ole servapõhine meetod, samas kui esimese sügavuse otsing on servapõhine meetod.Esimene sügavusotsing toimub rekursiivsel viisil, kus tippe uuritakse servade kaudu. Esimeses sügavusotsingus külastatakse igat tippu üks kord, mida kontrollitakse kaks korda.
Peamised erinevused
- Laiuse esimene otsing on graafikut läbiv meetod, mis kasutab järjekorda külastatud tippude salvestamiseks, samas kui sügavus esimene otsing on graafiku liikumise meetod, mis kasutab virna külastatud tippude salvestamiseks.
- Laiuse esimene otsing on tipupõhine algoritm, sügavuse esimene otsing on servapõhine algoritm
- Laiuse esimene otsing on mälu ebatõhus, samas kui esimese sügavuse otsing on mälu efektiivne.
- Uurib kahepoolset graafi, ühendatud komponenti ja graafil olevat lühimat rada, samas kui uuritakse kahe servaga ühendatud graafikut, tugevalt ühendatud graafi, atsüklilist graafi ja topoloogilist järjestust.
Järeldus
Ülaltoodud artiklis näeme selget erinevust esimese hingetõmbe ja põhjaliku otsingu vahel rakenduse vahel.
