Реализация алгоритма поиска в глубину на графе

Краткое описание алгоритма поиска в глубину

Алгоритм, как и при поиске в ширину, ищет кратчайший путь от заданной вершины до всех остальных. При этом обход осуществляется «в глубину» графа, то есть мы прыгаем на потомка, потом на следующего и так далее, пока есть куда углубляться. Как только достигнут «конец» возвращаемся на один уровень и опять углубляемся. Другими словами, мы не задерживаемся на одном уровне, а перемещаемся вверх и вниз.

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

Моя реализация поиска в глубину на c++

читать далее «Реализация алгоритма поиска в глубину на графе»

Реализация алгоритма поиска в ширину на графе

Краткое описание алгоритма поиска в ширину

Алгоритм ищет кратчайший путь, и его длину от заданной вершины до всех остальных. При этом просматривается последовательно каждый уровень соседей стартовой вершины. То есть мы в прямом смысле ходим в ширину по всему уровню. Подробнее вы всегда можете почитать на википедии. А вообще, если вы ищете реализацию, то уже знаете сам алгоритм, так что погнали реализовывать поиск в ширину!

Моя реализация поиска в ширину на c++

Граф представлен следующим образом. Массив(vector c++) из n элементов, где n — число вершин в графе. Каждый элемент массива соответствует вершине графа и содержит вложенный массив — список вершин, смежных с данной.


typedef vector< vector<int> > graphNotWeighted;

Функция реализации принимает на вход сам граф и номер стартовой вершины, отрабатывает, и заполняет два массива: массив расстояний от каждой вершины до стартовой, и массив предков каждой вершины на пути к стартовой. С помощью второго массива восстанавливается полный путь от стартовой вершины до всех остальных.

Исходный код алгоритма поиска в ширину на c++

читать далее «Реализация алгоритма поиска в ширину на графе»