Algoritmus na souvislost
Úloha číslo: 4100
Navrhněte algoritmus, který pro daný graf zjistí jeho komponenty souvislosti.
Řešení
Prohledáme graf, tak, že vrchol, jenž má souseda v nějaké komponentě, bude patřit do stejné. Vždy, když budeme muset novým vrcholem, začneme novou komponentu. Pseudokód algoritmu následuje:
- Inicializace: všem vrcholům grafu přiřaď prázdnou značku.
- \(i=0\)
- Dokud se v grafu nachází neoznačený vrchol \(u\), opakuj:
- \(i++\)
- Označ \(u\) pomocí \(i\)
- Dokud se v grafu nachází neoznačený vrchol \(v\) jehož soused má značku \(i\), označ \(v\) pomocí \(i\)
- Odpověď: graf má \(i\) komponent. Vrcholy se stejnou značkou leží ve stejné komponentě.