# Základy a Porovnanie prehľadávania grafov Grafy sú základnou dátovou štruktúrou v informatike, ktorá nám umožňuje modelovať vzťahy medzi rôznymi entitami. Prehľadávanie grafov je kľúčovou operáciou, ktorá nám pomáha analyzovať ich štruktúru, nachádzať cesty medzi vrcholmi a riešiť rôznorodé problémy. V tejto kapitole sa zameriame na dva najzákladnejšie a najpoužívanejšie algoritmy prehľadávania: Prehľadávanie do šírky (Breadth-First Search - BFS) a Prehľadávanie do hĺbky (Depth-First Search - DFS). Pochopenie ich princípov a rozdielov je nevyhnutné pre efektívne riešenie mnohých algoritmických úloh. ## Úvod do grafov > **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, webové stránky alebo akékoľvek iné entity, zatiaľ čo hrany reprezentujú vzťahy alebo spojenia medzi nimi, ako sú cesty, priateľstvá alebo odkazy. Hrany môžu byť **orientované** alebo **neorientované**. V neorientovanom grafe hrana $(u, v)$ znamená, že existuje spojenie medzi vrcholom $u$ a vrcholom $v$ v oboch smeroch. V orientovanom grafe (digrafe) hrana $(u, v)$ znamená, že existuje spojenie z vrcholu $u$ do vrcholu $v$, ale nie nevyhnutne aj opačným smerom. Grafy môžu byť tiež **vážené**, ak sú k hranám priradené číselné hodnoty (váhy), ktoré môžu reprezentovať napríklad vzdialenosť, čas alebo náklady. ## Reprezentácia grafov Pre prácu s grafmi v počítačových programoch je potrebné ich vhodne reprezentovať. Existujú dva hlavné spôsoby reprezentácie: ### 1. Matica susednosti (Adjacency Matrix) > **Matica susednosti** je štvorcová matica $A$ rozmeru $V \times V$, kde $V$ je počet vrcholov. Prvok $A[i][j]$ je $1$, ak existuje hrana z vrcholu $i$ do vrcholu $j$, a $0$ inak. Pre vážené grafy môže $A[i][j]$ obsahovať váhu hrany. Výhodou matice susednosti je rýchla kontrola existencie hrany (v čase $O(1)$), nevýhodou je pamäťová náročnosť $O(V^2)$ aj pre riedke grafy (s malým počtom hrán). ### 2. Zoznam susednosti (Adjacency List) > **Zoznam susednosti** udržiava pre každý vrchol $u$ zoznam všetkých vrcholov, ktoré sú s ním priamo spojené hranou. Napríklad, ak máme graf s vrcholmi $0, 1, 2, 3$, zoznam susednosti by mohol vyzerať takto: * $0$: $[1, 2]$ * $1$: $[3]$ * $2$: $[3]$ * $3$: $[]$ Výhodou zoznamu susednosti je efektívnejšia pamäťová náročnosť $O(V + E)$, kde $E$ je počet hrán, čo je výhodné pre riedke grafy. Nevýhodou je pomalšia kontrola existencie hrany (v čase $O(\text{stupeň vrcholu})$). Pre väčšinu algoritmov prehľadávania je zoznam susednosti preferovanou reprezentáciou. Did you know, že v reálnych sieťach, ako je internet alebo sociálne siete, sú grafy často extrémne riedke, a preto je zoznam susednosti oveľa efektívnejší než matica susednosti? ## Prehľadávanie do šírky (Breadth-First Search, BFS) BFS prehľadáva graf po vrstvách. Začína od počiatočného vrcholu a najprv 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 BFS 1. **Inicializácia:** Všetky vrcholy sú označené 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: a. Vyberie sa vrchol $u$ z frontu. b. Pre všetkých nenavštívených susedov $v$ vrcholu $u$: i. Označí sa $v$ ako navštívený. ii. Pridá sa $v$ do frontu. ### Vlastnosti a použitie BFS * **Najkratšia cesta v počte hrán:** Jednou z kľúčových vlastností BFS je, že ak sa aplikuje na nevážený graf, nájde najkratšiu cestu (v zmysle minimálneho počtu hrán) 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, čím zaručuje, že nájde všetky vrcholy vo vzdialenosti $k$ pred t