Поиск в ширину

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

Таким образом, основная идея поиска в ширину заключается в том, что сначала исследуются все вершины, смежные с начальной вершиной (вершина с которой начинается обход). Эти вершины находятся на расстоянии 1 от начальной. Затем исследуются все вершины на расстоянии 2 от начальной, затем все на расстоянии 3 и т.д. Обратим внимание, что при этом для каждой вершины сразу находятся длина кратчайшего маршрута от начальной вершины.

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

Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная (и заносится в очередь).

Шаг 2. Посещается первая вершина из очереди (если она не помечена как посещенная). Все ее соседние вершины заносятся в очередь. После этого она удаляется из очереди.

Шаг 3. Повторяется шаг 2 до тех пор, пока очередь не пуста.

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

//Описание функции алгоритма поиска в ширину

void Breadth_First_Search(int n, int **Graph, bool *Visited, int Node){

int *List = new int[n]; //очередь

int Count, Head; // указатели очереди

int i;

// начальная инициализация

for (i = 0; i < n ; i++)

List[i] = 0;

Count = Head = 0;

// помещение в очередь вершины Node

List[Count++] = Node;

Visited[Node] = true;

while (Head < Count) {

//взятие вершины из очереди

Node = List[Head++];

cout << Node + 1 << endl;

// просмотр всех вершин, связанных с вершиной Node

for (i = 0 ; i < n ; i++)

// если вершина ранее не просмотрена

if (Graph[Node][i] && !Visited[i]){

// заносим ее в очередь

List[Count++] = i;

Visited[i] = true;

}

}

}

Сложность поиска в ширину при нематричном представлении графа равна O(n+m), ибо рассматриваются все n вершин и m ребер. Использование матрицы смежности приводит к оценке O(n²)