Преимущества обхода графа в глубину для поиска компонент связности заключаются в следующем:

• Возможность посетить все вершины графа. 1 Для этого нужно каждый раз вызываться из любой непосещённой вершины, и в результате будут найдены все компоненты связности. 1
• Пометка всех вершин, лежащих в одной компоненте связности с данной, и только их. 3 Это происходит благодаря тому, что в каждую вершину алгоритм зайдёт не больше одного раза, потому что как только это произойдёт, вершина будет помечена как посещённая. 3
• Применимость в ситуациях, когда граф неизвестен целиком, а алгоритм выполняет какое-то автоматизированное устройство. 24 В таком случае поиск в глубину является практически оптимальным решением. 2