Каковы основные различия между алгоритмами обхода графа в ширину и глубину?

Некоторые основные различия между алгоритмами обхода графа в ширину (BFS, Breadth First Search) и в глубину (DFS, Depth First Search):

Направление обхода:

• BFS делает обход поуровнево: сначала проходит по всем ближайшим от начальной точки вершинам, потом спускается глубже. 1
• DFS ищет маршрут по графу «в глубину»: на каждом шаге «уходит» всё дальше. 2

Обработка вершин:

• BFS одновременно обрабатывает множество вершин. 8 Для каждой из них сразу находится длина кратчайшего маршрута от начальной вершины. 6
• DFS в каждый момент исполнения алгоритма обрабатывает только одну вершину. 8 Если возможные пути по рёбрам, выходящим из вершин, разветвляются, нужно сначала полностью исследовать одну ветку и только потом переходить к другим веткам (если они останутся нерассмотренными). 56

Поиск путей:

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