Graf a prehľadávanie do šírky a do hĺbky

Podcast

Základy a Porovnanie prehľadávania grafov0:00 / 12:41

0:001:00 zostáva

1x

Grafy sú základnou dátovou štruktúrou v informatike, ktorá nám pomáha modelovať komplexné vzťahy medzi objektmi. Pre efektívne spracovanie týchto vzťahov slúžia algoritmy prehľadávania, medzi ktorými vynikajú prehľadávanie do šírky (BFS) a prehľadávanie do hĺbky (DFS). Pochopenie princípov týchto algoritmov je kľúčové pre študentov informatiky a je častou témou na skúškach a maturite.

Graf a prehľadávanie do šírky a do hĺbky: Úvod do základov

Graf G je definovaný ako usporiadaná dvojica (V, E), kde V je konečná neprázdna množina vrcholov (uzlov) a E je množina hrán, ktoré spájajú dvojice vrcholov. Vrcholy môžu reprezentovať napríklad mestá, osoby alebo webové stránky, zatiaľ čo hrany predstavujú vzťahy alebo spojenia. Hrany môžu byť orientované (jednosmerné) alebo neorientované (obojsmerné).

Grafy môžu byť tiež vážené, ak sú k hranám priradené číselné hodnoty, ktoré môžu reprezentovať vzdialenosť, čas alebo náklady. Pre prácu s grafmi v programoch je dôležitá ich správna reprezentácia.

Reprezentácia grafov v informatike

Pre počítačové spracovanie grafov sa používajú dva hlavné spôsoby:

• Matica susednosti (adjacency matrix): Ide o štvorcovú maticu A rozmeru V × V. Prvok A[i][j] je 1, ak existuje hrana z vrcholu i do vrcholu j, inak je 0. Pre vážené grafy obsahuje A[i][j] váhu hrany. Výhodou je rýchla kontrola existencie hrany (v čase O(1)), ale pamäťová náročnosť je O(V²).
• Zoznam susednosti (adjacency list): Pre každý vrchol u sa udržiava zoznam všetkých vrcholov, ktoré sú s ním priamo spojené hranou. Napríklad, vrchol 0 môže mať zoznam [1, 2]. Pamäťová náročnosť je efektívnejšia O(V + E), čo je výhodné pre riedke grafy. Pre väčšinu algoritmov prehľadávania je zoznam susednosti preferovanou reprezentáciou.

Prehľadávanie do šírky (BFS) – Breadth-First Search

Algoritmus BFS systematicky navštevuje vrcholy grafu po vrstvách. Začína od počiatočného vrcholu, navštívi všetkých jeho priamych susedov, potom susedov susedov a tak ďalej. Používa dátovú štruktúru front (FIFO – First-In, First-Out) na udržanie poradia vrcholov, ktoré je potrebné navštíviť.

Princíp a vlastnosti algoritmu BFS

1. Inicializácia: Všetky vrcholy sa označia ako nenavštívené. Vytvorí sa front a pridá sa do neho počiatočný vrchol. Počiatočný vrchol sa označí ako navštívený.
2. Opakované kroky: Kým front nie je prázdny:

• Vyberie sa vrchol u z frontu.
• Pre všetkých nenavštívených susedov v vrcholu u:
• Označí sa v ako navštívený.
• Pridá sa v do frontu.

Kľúčové vlastnosti a použitie BFS:

• Časová zložitosť: O(V + E), kde V je počet vrcholov a E je počet hrán. Každý vrchol a každá hrana sú spracované konštantný počet krát.
• Najkratšia cesta: Nájde najkratšiu cestu (v počte hrán) v nevážených grafoch z počiatočného vrcholu do všetkých ostatných dosiahnuteľných vrcholov. Je to preto, že BFS prehľadáva graf po vrstvách.
• Použitie: Hľadanie najkratšej cesty v nevážených grafoch, identifikácia komponentov súvislosti, detekcia cyklov v neorientovaných grafoch, web crawler.

Príklad krokovania BFS

Majme neorientovaný graf s vrcholmi A, B, C, D, E, F a hranami: (A,B), (A,C), (B,D), (C,E), (D,F), (E,F). Začnime z vrcholu A.

1. Inicializácia: Front: [], Navštívené: {}, Vzdialenosti: {A:0, B:∞, C:∞, D:∞, E:∞, F:∞}, Predchodcovia: {A:null,...}
2. Krok 1: Pridaj A do frontu, označ A ako navštívené, vzdialenosť A = 0. Front: [A], Navštívené: {A}
3. Krok 2: Vyber A z frontu. Susedia A sú B, C.

• Pre B: Označ B, pridaj B do frontu, vzdialenosť B = 1, predchodca B = A.
• Pre C: Označ C, pridaj C do frontu, vzdialenosť C = 1, predchodca C = A.
• Front: [B, C], Navštívené: {A, B, C}, Vzdialenosti: {A:0, B:1, C:1,...}

4. Krok 3: Vyber B z frontu. Susedia B sú A, D. A je navštívené, ignoruj. Pre D: Označ D, pridaj D do frontu, vzdialenosť D = 2, predchodca D = B. Front: [C, D], Navštívené: {A, B, C, D}, Vzdialenosti: {A:0, B:1, C:1, D:2,...}
5. Krok 4: Vyber C z frontu. Susedia C sú A, E. A je navštívené, ignoruj. Pre E: Označ E, pridaj E do frontu, vzdialenosť E = 2, predchodca E = C. Front: [D, E], Navštívené: {A, B, C, D, E}, Vzdialenosti: {A:0, B:1, C:1, D:2, E:2,...}
6. Krok 5: Vyber D z frontu. Susedia D sú B, F. B je navštívené, ignoruj. Pre F: Označ F, pridaj F do frontu, vzdialenosť F = 3, predchodca F = D. Front: [E, F], Navštívené: {A, B, C, D, E, F}, Vzdialenosti: {A:0, B:1, C:1, D:2, E:2, F:3}
7. Krok 6: Vyber E z frontu. Susedia E sú C, F. C a F sú navštívené, ignoruj. Front: [F]
8. Krok 7: Vyber F z frontu. Susedia F sú D, E. D a E sú navštívené, ignoruj. Front: []

Front je prázdny, BFS je dokončené. Najkratšia cesta z A do F je A → B → D → F (dĺžka 3 hrany) alebo A → C → E → F (dĺžka 3 hrany).

Prehľadávanie do hĺbky (DFS) – Depth-First Search

Algoritmus DFS prehľadáva graf tak, že ide čo najhlbšie do jednej vetvy, kým nenarazí na vrchol, ktorý už nemá nenavštívených susedov. Potom sa vracia späť (backtrackuje) a skúma ďalšie vetvy. Používa dátovú štruktúru zásobník (LIFO – Last-In, First-Out) alebo rekurziu, ktorá implicitne využíva zásobník volaní.

Princíp a charakteristika algoritmu DFS

Princíp DFS (rekurzívna verzia):

1. Funkcia DFS(u):

• Označ u ako navštívené.
• Pre každého nenavštíveného suseda v vrcholu u:
• Zavolaj DFS(v).

Kľúčové vlastnosti a použitie DFS:

• Časová zložitosť: O(V + E), rovnako ako BFS, pretože každý vrchol a každá hrana sú spracované konštantný počet krát.
• Použitie: Detekcia cyklov v orientovaných aj neorientovaných grafoch, topologické triedenie (Topologické triedenie je kľúčové pre plánovanie úloh), hľadanie silne súvislých komponentov, riešenie bludísk, generovanie stromov.

Príklad krokovania DFS

Použijeme rovnaký graf ako pre BFS. Začnime z vrcholu A.

1. Inicializácia: Všetky vrcholy sú nenavštívené. Zásobník volaní je prázdny. Navštívené: {}
2. Krok 1: Zavolaj DFS(A). Označ A. Navštívené: {A}. Susedia A: B, C.
3. Krok 2: Vo vnútri DFS(A), zavolaj DFS(B). Označ B. Navštívené: {A, B}. Susedia B: A, D. A je navštívené. Zavolaj DFS(D).
4. Krok 3: Vo vnútri DFS(D), zavolaj DFS(D). Označ D. Navštívené: {A, B, D}. Susedia D: B, F. B je navštívené. Zavolaj DFS(F).
5. Krok 4: Vo vnútri DFS(F), zavolaj DFS(F). Označ F. Navštívené: {A, B, D, F}. Susedia F: D, E. D je navštívené. Zavolaj DFS(E).
6. Krok 5: Vo vnútri DFS(E), zavolaj DFS(E). Označ E. Navštívené: {A, B, D, F, E}. Susedia E: C, F. F je navštívené. Zavolaj DFS(C).
7. Krok 6: Vo vnútri DFS(C), zavolaj DFS(C). Označ C. Navštívené: {A, B, D, F, E, C}. Susedia C: A, E. A a E sú navštívené. Všetci susedia C sú navštívení. Návrat z DFS(C).
8. Krok 7: Návrat do DFS(E). Všetci susedia E sú navštívení. Návrat z DFS(E).
9. Krok 8: Návrat do DFS(F). Všetci susedia F sú navštívení. Návrat z DFS(F).
10. Krok 9: Návrat do DFS(D). Všetci susedia D sú navštívení. Návrat z DFS(D).
11. Krok 10: Návrat do DFS(B). Všetci susedia B sú navštívení. Návrat z DFS(B).
12. Krok 11: Návrat do DFS(A). Všetci susedia A sú navštívení. Návrat z DFS(A).

Poradie navštívenia vrcholov (prvýkrát, keď boli objavené) je A, B, D, F, E, C.

Porovnanie BFS a DFS: Kedy ktorý použiť?

Oba algoritmy sú efektívne pre prehľadávanie grafov a majú rovnakú asymptotickú časovú zložitosť O(V + E). Líšia sa však v spôsobe prehľadávania a v tom, aké problémy riešia najlepšie:

• BFS: Prehľadáva po vrstvách a garantuje nájdenie najkratšej cesty v nevážených grafoch. Je vhodný pre problémy, kde je dôležitá vzdialenosť od štartu.
• DFS: Prehľadáva do hĺbky. Je vhodnejší pre problémy, kde je dôležitá štruktúra cesty alebo cykly, napríklad topologické triedenie alebo hľadanie silne súvislých komponentov.

Simulácia krokovania algoritmov pomáha pochopiť, prečo BFS nájde najkratšiu cestu (vždy spracuje všetky vrcholy na danej úrovni pred prechodom na ďalšiu) a prečo DFS preferuje hlbšie vetvy (kvôli princípu LIFO zásobníka).

Bežné chyby a mylné predstavy pri práci s grafmi

Pri implementácii a používaní algoritmov prehľadávania grafov sa študenti často stretávajú s určitými problémami:

• Zabudnutie na označenie navštívených vrcholov: Bez označovania navštívených vrcholov môžu algoritmy vstúpiť do nekonečnej slučky v grafoch s cyklami alebo opakovane spracovávať rovnaké vrcholy, čo vedie k neefektívnosti či nesprávnym výsledkom.
• Nesprávna dátová štruktúra: Použitie zásobníka namiesto frontu pre BFS alebo naopak pre DFS zmení správanie algoritmu a výsledok nebude zodpovedať očakávaniam (napríklad BFS už nenájde najkratšiu cestu).
• Predpokladanie najkratšej cesty v vážených grafoch pomocou BFS: BFS nájde najkratšiu cestu len v počte hrán. Pre vážené grafy sú potrebné iné algoritmy, ako napríklad Dijkstrov algoritmus alebo Bellmanov-Fordov algoritmus.
• Nezohľadnenie nesúvislých grafov: Ak graf nie je súvislý (skladá sa z viacerých komponentov súvislosti), štandardné volanie BFS alebo DFS z jedného počiatočného vrcholu navštívi len vrcholy v jeho komponente. Pre prehľadanie celého grafu je potrebné volať algoritmus opakovane pre každý nenavštívený vrchol.

Význam simulácie algoritmov prehľadávania

Interaktívna simulácia prehľadávania grafov je neoceniteľným nástrojom pre študentov. Umožňuje vizualizovať kroky algoritmov BFS a DFS v reálnom čase. Študent môže:

• Krokovať BFS a DFS: Pozorovať, ako sa algoritmy postupne šíria grafom, označujú navštívené vrcholy a pridávajú ich do frontu/zásobníka. To pomáha pochopiť vnútornú logiku a rozdiel medzi prehľadávaním do šírky a do hĺbky.
• Meniť počiatočný vrchol: Vidieť, ako voľba počiatočného vrcholu ovplyvňuje poradie navštívenia ostatných vrcholov a výsledné cesty.
• Experimentovať s rôznymi štruktúrami grafov: Vytvárať riedke, husté, cyklické alebo acyklické grafy a pozorovať, ako sa algoritmy správajú v rôznych scenároch. Napríklad, v acyklickom grafe (strome) sa oba algoritmy správajú podobne, ale v grafoch s cyklami sa ich cesty výrazne líšia.
• Vizualizovať najkratšiu cestu: Pri BFS simulácia často zvýrazňuje nájdenú najkratšiu cestu k cieľovému vrcholu, čo upevňuje pochopenie tejto kľúčovej vlastnosti.

Simulácia poskytuje praktickú skúsenosť, ktorá dopĺňa teoretické znalosti a pomáha pri riešení komplexnejších problémov s grafmi.

Najčastejšie otázky študentov o BFS a DFS

Aký je hlavný rozdiel medzi BFS a DFS?

Hlavný rozdiel spočíva v poradí, v akom navštevujú vrcholy. BFS (prehľadávanie do šírky) prehľadáva graf po vrstvách, najprv všetkých susedov daného vrcholu, potom susedov susedov atď., zatiaľ čo DFS (prehľadávanie do hĺbky) sa snaží ísť čo najhlbšie do jednej vetvy predtým, než sa vráti a preskúma iné vetvy.

Ktorý algoritmus nájde najkratšiu cestu?

BFS nájde najkratšiu cestu v nevážených grafoch z hľadiska minimálneho počtu hrán. Pre vážené grafy sú potrebné iné algoritmy, ako napríklad Dijkstrov algoritmus.

Prečo je časová zložitosť oboch algoritmov O(V + E)?

Oba algoritmy navštívia každý vrchol a preskúmajú každú hranu v grafe len konštantný počet krát. V je počet vrcholov a E je počet hrán. Preto je ich časová zložitosť rovnaká.

Kedy použiť BFS a kedy DFS?

BFS je vhodný pre hľadanie najkratších ciest v nevážených grafoch, prechádzanie všetkých uzlov na rovnakej úrovni (napr. úroveň 2, úroveň 3), alebo pre webové crawlere. DFS je lepší pre detekciu cyklov, topologické triedenie, hľadanie silne súvislých komponentov alebo pri riešení problémov ako sú bludiská.