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

Обход графа — посещение всех ребер графа в заданной последовательности.

Обход графа может использоваться, например, для нахождения компонент связности, для поиска путей в графе, для поиска вершин и расчета для них разных величин (глубина и т.д.).

Поиск в ширину – алгоритм, который находит кратчайший путь от заданной вершины до всех остальных за O(n + m).

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

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

#include<stdio.h>
#include<stdbool.h>

int MAXN = 100;//Максимальное число вершин
int a[MAXN][MAXN];//Матрица смежности
int minpath[MAXN];//Массив расстояний до i-ой вершины
int que[MAXN];//Сама очередь
int qe = -1;//Указатель на конец очереди
int qb = -1;//Указатель на начало очереди
int n;//Число вершин
int first;//Начальная вершина

void put(int x; int len)
{
    //Проверим, улучшим ли мы путь до вершины x
    if (minpath[x] = -1 || minpath[x] > len)
{
        //Кладем новую вершину в очередь
        qe++;
        que[qe] = x; 
        //Записываем для нее новое расстояние
        minpath[x] = len;
    }
}

void get(int *x; int *len)
{
    //Извлекаем из очереди следующую вершину
    qb++;
    *x = que[qb];
    //И извлекаем для нее уже найденный путь
    *len = minpath[*x];
}

int main()
{
    scanf(“%d%d”, &n, &first);
    //Считываем количество вершин и начальную вершину
    for (int i = 0; i < n; i++)
{
        minpath[i] = -1;
        //Устанавливаем начальные значения минимальных путей
        for (int j = 0; j < n; j++)
            scanf(“%d”, a[i][j]); 
            //Читаем матрицу смежности
    }
    put(first, 0);
    //Кладем первый элемент
    while (qe > qb)
{/*Пока в очереди есть элементы*/
        int x, len;
        get(&x, &len);
        //Извлекаем очередную вершину

        for (int i = 0; i < n; i++)
            if (a[x][i])//Если есть ребро из x в i
                put(i, len + 1);//Путь увеличивается на одно ребро!
    }
    /*Сейчас в массиве minpath будут расстояния от вершины first до всех остальных вершин*/
}