Алгоритмы обхода в ширину и в глубину отличаются подходом к исследованию графа. 2

Обход в ширину заключается в том, что сначала исследуются смежные вершины, а уже потом вершины на следующем уровне. 2 То есть сначала исследуются все вершины, смежные с начальной вершиной, затем все вершины на расстоянии 2 от начальной, затем все на расстоянии 3 и так далее. 2

Обход в глубину отличается более агрессивным продвижением по графу. 3 Он всегда сразу продвигается к самой отдалённой от стартовой вершины и затем, если не может продвинуться дальше, отступает назад. 3

Кроме того, для хранения информации о посещённых вершинах у обоих алгоритмов используются различные структуры данных: обход в глубину использует стек для хранения текущего пути, а обход в ширину — очередь для хранения вершин, ожидающих обработки. 4