Test na Graf a prohledávání do šířky a do hloubky

Otázka 1: Paměťová náročnost seznamu sousednosti je méně efektivní pro řídké grafy než paměťová náročnost matice sousednosti.

A. Ano

B. Ne

Vysvětlení: Podle studijních materiálů je paměťová náročnost seznamu sousednosti O(V + E), což je efektivnější pro řídké grafy než paměťová náročnost matice sousednosti, která je O(V²). Tedy, seznam sousednosti je pro řídké grafy paměťově efektivnější, nikoliv méně efektivní.

Otázka 2: Proč je matice sousednosti obzvláště vhodná pro reprezentaci hustých grafů?

A. Umožňuje rychle zjistit, zda existuje hrana mezi dvěma vrcholy s časovou složitostí O(1).

B. Má paměťovou náročnost O(V + E), což je efektivní i pro řídké grafy.

C. Procházení všech sousedů daného vrcholu je velmi rychlé s časovou složitostí O(stupně vrcholu).

D. U hustých grafů, kde je mnoho hran, se efektivně využívá většina paměti alokované pro matici.

Vysvětlení: Matice sousednosti je vhodná pro husté grafy, protože umožňuje velmi rychle zjistit existenci hrany mezi dvěma vrcholy (O(1)). Dále, jelikož husté grafy obsahují mnoho hran, většina prvků matice sousednosti nebude nulová, což znamená efektivní využití alokované paměti O(V²). Možnost B a C popisují výhody seznamu sousednosti, nikoli matice sousednosti.

Otázka 3: Hlavním principem prohledávání do šířky (BFS) je systematické prozkoumávání grafu po vrstvách.

A. Ano

B. Ne

Vysvětlení: Podle studijních materiálů je hlavním principem prohledávání do šířky (BFS) systematické prozkoumávání grafu po vrstvách. Algoritmus začíná od počátečního vrcholu, navštíví všechny jeho přímé sousedy, poté všechny nenavštívené sousedy těchto sousedů a tak dále, dokud nejsou dosaženy všechny dosažitelné vrcholy.

Otázka 4: Co se děje s vrcholy grafu během inicializace BFS algoritmu PŘED zpracováním startovního vrcholu?

A. Jsou označeny jako navštívené a jejich vzdálenost se nastaví na 0.

B. Jsou označeny jako nenavštívené, jejich vzdálenost se nastaví na nekonečno a jejich předchůdce na null.

C. Jsou přidány do fronty a jejich předchůdce je nastaven na startovní vrchol.

D. Jsou náhodně označeny jako navštívené nebo nenavštívené.

Vysvětlení: Podle studijních materiálů je v kroku 'Inicializace' uvedeno: 'Všechny vrcholy v grafu jsou označeny jako nenavštívené. Pro každý vrchol si můžeme uložit jeho vzdálenost od startovního vrcholu (počáteční hodnota nekonečno) a jeho předchůdce (počáteční hodnota null).' Možnost 1 přesně vystihuje tuto inicializační fázi.

Otázka 5: Při spuštění algoritmu DFS z počátečního vrcholu A, se podle uvedeného příkladu přidá vrchol C do zásobníku před vrcholem D.

A. Ano

B. Ne

Vysvětlení: Příklad DFS jasně uvádí: "B není navštívené: Označíme B, přidáme B do zásobníku. Zásobník = [B]. (DFS se nyní ponoří do B, než se vrátí k C)." Poté se zpracovává vrchol B, z něj D, a D je přidáno do zásobníku. Teprve po dokončení prohledávání větve z B (včetně D a F) by se algoritmus vrátil k A a zpracoval by C. Proto je D přidáno do zásobníku před C.