Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Souvislost

Definice

Cesta v grafu z vrcholu do vrcholu je posloupnost taková, že , a pro všechna , je . Graf je souvislý, pokud pro každé dva vrcholy existuje v cesta z do . Toto platí pro orientované i neorientované grafy.

Algoritmus (Testování souvislosti grafu/počítání komponent souvislosti)

Algoritmus využívá prohledávání do šířky (nebo do hloubky) - v 1 kroku vždy najde dosud nenavštívený vrchol, začne z něj procházet graf a takto projde(oddělí) jednu komponentu souvislosti. Pokud skončí po prvním kroku, graf je souvislý. Počet kroků, potřebných k navštívení všech vrcholů grafu, je zároveň počtem komponent souvislosti.

Časová složitost je , protože o algoritmu platí to samé co o prohledávání do šířky - žádný vrchol nebude přidán do fronty více než jednou a testován více než 2x pro každou hranu.