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ě.
Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze