Обход графа в компьютерных алгоритмах — это процесс систематического просмотра всех вершин или рёбер графа, чтобы найти некоторые вершины, удовлетворяющие определённым условиям. 2

Некоторые алгоритмы обхода графов:

• Обход в глубину (DFS). 14 Алгоритм начинается с выбранной «корневой» вершины и итеративно переходит от текущей вершины к соседней, не посещаемой вершине, пока больше не сможет найти неисследованную вершину для перехода из её текущего местоположения. 4 Затем алгоритм возвращается по ранее посещённым вершинам, пока не найдёт вершину, соединённую с ещё более неизведанной территорией. 4
• Обход в ширину (BFS). 25 Сначала исследуются все вершины, смежные с начальной вершиной (вершина, с которой начинается обход). 2 Затем исследуются все вершины на расстоянии 2 от начальной, затем все на расстоянии 3 и так далее. 2
• Алгоритм Дейкстры. 5 Предназначен для нахождения кратчайших путей от одной вершины взвешенного графа до всех остальных вершин. 5 Для корректной работы алгоритма необходимо, чтобы в графе отсутствовали рёбра с отрицательными весами. 5