Kartičky na Graf a prehľadávanie do šírky a do hĺbky
Graf a prehľadávanie do šírky a do hĺbky (BFS, DFS) – Návod pre študentov
Ťukni na otočenie · Potiahni na navigáciu
Základy a Porovnanie prehľadávania grafov
26 kartičiek
Kartička 1
Otázka: Čo je to graf v informatike a diskrétnej matematike?
Odpoveď: Graf je základná dátová štruktúra, ktorá slúži na modelovanie vzťahov medzi objektmi. Je definovaný ako usporiadaná dvojica (V, E), kde V je množina v
Kartička 2
Otázka: Aký je rozdiel medzi orientovanou a neorientovanou hranou v grafe?
Odpoveď: V neorientovanom grafe hrana (u, v) znamená spojenie medzi u a v v oboch smeroch. V orientovanom grafe (digrafe) hrana (u, v) znamená spojenie len z u
Kartička 3
Otázka: Kedy sa graf nazýva vážený?
Odpoveď: Graf je vážený, ak sú k hranám priradené číselné hodnoty (váhy), ktoré môžu reprezentovať napríklad vzdialenosť, čas alebo náklady.
Kartička 4
Otázka: Aké sú dva hlavné spôsoby reprezentácie grafov v počítačových programoch?
Odpoveď: Dva hlavné spôsoby sú matica susednosti (adjacency matrix) a zoznam susednosti (adjacency list).
Kartička 5
Otázka: Ako funguje matica susednosti pre reprezentáciu grafu?
Odpoveď: Matica susednosti je štvorcová matica A rozmeru V × V, kde A[i][j] je 1, ak existuje hrana z vrcholu i do vrcholu j (alebo váha hrany pre vážené grafy
Kartička 6
Otázka: Aké sú výhody a nevýhody matice susednosti?
Odpoveď: Výhodou je rýchla kontrola existencie hrany (O(1)). Nevýhodou je pamäťová náročnosť O(V²) aj pre riedke grafy.
Kartička 7
Otázka: Ako funguje zoznam susednosti pre reprezentáciu grafu?
Odpoveď: Pre každý vrchol u sa udržiava zoznam všetkých vrcholov, ktoré sú s ním priamo spojené hranou.
Kartička 8
Otázka: Aké sú výhody a nevýhody zoznamu susednosti?
Odpoveď: Výhodou je efektívnejšia pamäťová náročnosť O(V + E), výhodné pre riedke grafy. Nevýhodou je pomalšia kontrola existencie hrany (O(stupeň vrcholu)).
Kartička 9
Otázka: Ktorá reprezentácia grafov je preferovaná pre väčšinu algoritmov prehľadávania?
Odpoveď: Zoznam susednosti je preferovanou reprezentáciou pre väčšinu algoritmov prehľadávania.
Kartička 10
Otázka: Čo je cieľom prehľadávania grafov?
Odpoveď: Cieľom prehľadávania grafov je systematické navštevovanie všetkých vrcholov a hrán grafu s cieľom nájsť konkrétny vrchol, zistiť vlastnosti grafu aleb