Kartičky na Graf a prohledávání do šířky a do hloubky
Graf a Prohledávání do Šířky a Hloubky (BFS, DFS) – Kompletní Průvodce
Klepni pro otočení · Swipni pro navigaci
Reprezentace grafů
9 kartiček
Kartička 1
Otázka: Jaké dva hlavní způsoby reprezentace grafů existují?
Odpověď: Matice sousednosti a seznam sousednosti.
Kartička 2
Otázka: Jak je definována matice sousednosti?
Odpověď: Jako čtvercová matice o rozměrech V × V, kde V je počet vrcholů. Prvek A[i][j] je 1 (nebo váha hrany) pokud existuje hrana z i do j, jinak 0 (nebo nek
Kartička 3
Otázka: Jaké jsou výhody matice sousednosti?
Odpověď: Rychlé zjištění existence hrany (O(1)) a snadná implementace pro husté grafy.
Kartička 4
Otázka: Jaké jsou nevýhody matice sousednosti?
Odpověď: Paměťová náročnost O(V²) a pomalé procházení sousedů vrcholu (O(V)).
Kartička 5
Otázka: Jak je definován seznam sousednosti?
Odpověď: Jako pole seznamů (nebo spojových seznamů), kde pro každý vrchol i existuje seznam obsahující všechny vrcholy j, do kterých vede hrana z i.
Kartička 6
Otázka: Co se ukládá v seznamu sousednosti pro vážené grafy?
Odpověď: Dvojice (sousední vrchol, váha hrany).
Kartička 7
Otázka: Jaké jsou výhody seznamu sousednosti?
Odpověď: Paměťová náročnost O(V + E) a rychlé procházení všech sousedů daného vrcholu (O(stupeň vrcholu)).
Kartička 8
Otázka: Jaké jsou nevýhody seznamu sousednosti?
Odpověď: Zjištění existence hrany mezi dvěma vrcholy vyžaduje prohledání seznamu sousedů (O(stupeň vrcholu)).
Kartička 9
Otázka: Která reprezentace je obvykle preferována pro algoritmy prohledávání grafů, zejména u řídkých grafů?
Odpověď: Seznam sousednosti.