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

• Поиск кратчайшего пути. 12 Алгоритмы, такие как Дейкстры и Беллмана-Форда, применяются в картографических сервисах для прокладки маршрутов и определения местоположения. 1
• Обнаружение циклов. 1 Для этого используются, например, алгоритмы Флойда и Брента. 1 Они используются в распределённых алгоритмах, для обработки крупных графов, обнаружения взаимоблокировок в системах с параллельным выполнением и в криптографических приложениях. 1
• Поиск минимального остовного дерева. 1 Алгоритмы, такие как Прима и Крускала, применяются для создания деревьев для распределения данных в компьютерных сетях, в кластерном анализе с использованием графов, при сегментации изображений и в социально-географическом районировании. 1
• Поиск в пространстве состояний. 2 С помощью обходов графов можно найти решение задачи с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа. 2
• Нахождение кратчайшего цикла. 2
• Нахождение всех вершин и рёбер, лежащих на каком-либо кратчайшем пути между двумя вершинами. 2

Основными алгоритмами обхода графов являются поиск в глубину (DFS) и поиск в ширину (BFS). 3