Для пошуку компонент зв'язності використовується звичайний DFS практично без модифікацій (можна використовувати BFS). При запуску обходу з однієї вершини, він гарантовано відвідає всі вершини, до яких можна дістатися, тобто всю компоненту зв'язності, До якої належить початкова вершина.
Компоненти сильної зв'язності у графі можна знайти за допомогою пошуку в глибину в 3 етапи: Побудувати граф зі зворотними (інвертованими) ребрами Виконати у пошук у глибину та знайти — час закінчення обробки вершини Виконати пошук у глибину в , перебираючи вершини у зовнішньому циклі в порядку зменшення
Зв'язковий граф є своєю єдиною компонентою зв'язності. На рис. 4.21 зображено граф, Котрий має три компоненти зв'язності.