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

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

Однако у этого алгоритма нет возможности найти кратчайшие пути. 1