Разница между поиском в ширину и глубиной в теории графов заключается в подходе к обходу графа. 15

Поиск в ширину (breadth-first search, BFS) заключается в том, чтобы исследовать вершины графа послойно, в порядке увеличения расстояния от стартовой вершины. 5 Сначала алгоритм изучает все вершины, смежные с начальной, затем — на расстоянии 2 от неё, потом — на расстоянии 3 и так далее. 13 Для каждой вершины сразу вычисляется длина кратчайшего маршрута от начальной. 13

Поиск в глубину (depth-first search, DFS) отличается более агрессивным продвижением по графу. 5 Алгоритм всегда сразу продвигается к самой отдалённой от стартовой вершине и затем, если не может продвинуться дальше, отступает назад. 5 Когда возможные пути по рёбрам, выходящим из вершин, разветвляются, сначала полностью исследуется одна ветка, и только потом — другие (если они останутся нерассмотренными). 12

Кроме того, при поиске в глубину подграф предшествования может состоять из нескольких деревьев, так как поиск может выполняться из нескольких исходных вершин. 2 При поиске в ширину, в свою очередь, подграф предшествования образует одно дерево. 2