K čemu algoritmus slouží?

Ke zjištění, jestli dva vrcholy náleží téže komponentě.

Časová složitost

• O(|V| + |E|) – každá hrana i vrchol jsou procházeny maximálně jednou

Vstup

• graf G(V,E)
• dva zkoumané vrcholy V₀ a V₁

Inicializace

• V₀ … počáteční vrchol, z nějž spouštíme prohledávání (jeden ze zkoumaných vrcholů)

Postup

• Spustíme prohledávání grafu do šířky nebo do hloubky z jednoho zkoumaného vrcholu.
• V průběhu prohledávání testujeme, jestli jsme se dostali do druhého zkoumaného vrcholu.
• Pokud ano, oba vrcholy leží v téže komponentě.
• Pokud jsme ukončili prohledávání a nedostali jsme se do druhého zkoumaného vrcholu, vrcholy leží každý v jiné komponentě.

Výstup

• Informace o tom, jestli zkoumané vrcholy leží v téže komponentě.