Що таке компонент зв'язності у графі?

Просто кажучи, компонента зв'язності – частина графа (підграф), що є зв'язковий. Формально, компонента зв'язності – Набір вершин графа, між будь-якою парою яких існує шлях. Граф на ілюстрації містить три компоненти зв'язності, зафарбовані різними кольорами.

Кількість компонент зв'язності одно числу множин у системі множин, що не перетинаються. Кількість множин дорівнює числу представників, саме кількості таких v, котрим parent[v] = v. У прикладі є три представники: 3, 5 та 6. Тобто в графі є три компоненти зв'язності.

Зв'язковий граф є своєю єдиною компонентою зв'язності. На рис. 4.21 зображено граф, Котрий має три компоненти зв'язності.