Prohledávání do šířky (Breadth-first Search)
Prohledávání do šířky (BFS) je základní grafový algoritmus pro procházení grafu. Tento algoritmus systematicky prochází graf od počátečního uzlu, pro dočasné ukládání nenavštívených uzlů používá frontu.
Pseudokód
- Všem uzlům x nastav příznak VISIT(x) = FALSE.
- Počátečnímu uzlu s nastav příznak VISIT(x) = TRUE.
- Vlož počáteční uzel do fronty.
- Vezmi první uzel z fronty a označ jej u.
- Každý uzel v, do kterého vede hrana z uzlu u a jeho příznak VISIT(v) je roven FALSE, přidej na konec fronty a změň jeho příznak VISIT(v) = TRUE.
- Krok 4 opakuj tak dlouho, dokud není fronta prázdná.
Asymptotická složitost
Asymptotická složitost algoritmu je:
- V – počet uzlů
- E – počet hran
Příklad
Mějme následující graf. Počátečním uzlem je START, sousední uzly budou do fronty přidávány v abecedním pořadí.
ukázka průchodu grafem pomocí algoritmu BFS
Algoritmus bude postupovat v následujících krocích:
| Krok | Fronta (první prvek: vlevo) | Navštívené uzly |
|---|---|---|
| 1 | START | – |
| 2 | E, G | START |
| 3 | G, B, C, D | START, E |
| 4 | B, C, D | START, E, G |
| 5 | C, D | START, E, G, B |
| 6 | D | START, E, G, B, C |
| 7 | F | START, E, G, B, C, D |
| 8 | – | START, E, G, B, C, D, F |
Uzly byly navštíveny v tomto pořadí: START, E, G, B, C, D, F
začátek průchodu
další krok
další krok
další krok
další krok