Paieška platyn ir gilyn
Paieškos grafuose aplanko pasiekiamas viršūnes skirtinga tvarka.
Esminės žinios
BFS paeiliui nagrinėja sluoksnius pagal atstumą, matuojamą briaunų skaičiumi; DFS eina per neaplankytas gretimas viršūnes ir grįžta atgal. Naudojant gretimumo sąrašus ir pastovios sąnaudos patikras, ar viršūnė aplankyta, viso grafo apėjimo laiko sudėtingumas yra O(|V|+|E|). BFS nustato trumpiausius atstumus nesvertiniame grafe; DFS nebūtinai.
Sąlygos ir taikymo ribos
- Paieška iš vienos pradinės viršūnės apima tik pasiekiamas viršūnes; norint apeiti visą grafą, paiešką reikia iš naujo pradėti nuo neaplankytų viršūnių.
- Prielaidos apie grafo vaizdavimą ir pagalbinių duomenų tvarkymą yra sudėtingumo įverčio dalis.
Šaltiniai · 2
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Massachusetts Institute of Technology2 šaltiniai
Pagrindimas ir peržiūra
Grafų apibrėžimai, gretimumo vaizdavimo būdai, briaunų skaičiumi matuojami atstumai ir BFS trumpiausi keliai. Pasiekiamumas taikant paiešką į gylį, viso grafo apėjimas, O(V+E) įvertis ir skirtumas nuo BFS trumpiausių kelių.
2026-10-10 · BFS ir DFS veikimas, pasiekiamumas ir viso grafo apėjimo sąnaudos.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-graph-traversal
- Versija
- university-reference.1
- Struktūruotas žinyno įrašas
- Universitetinis žinynas