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

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

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

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

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

typedef vector< vector<int> > graphNotWeighted;

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

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

void BFS(graphNotWeighted &G, int start) {
    queue<int> Q;
    //distance[i] - расстояние от i-ой вершины до стартовой
    vector<int> distance(G.size(), -1);
    //prevTop[i] - предок i-ой вершины в кратчайшем пути
    vector<int> prevTop(G.size(), -1);

    distance[start] = 0;
    Q.push(start);
    while (Q.size()) {
        int u = Q.front();
        Q.pop();
        for (int j = 0; j < G[u].size(); j++) {
            int v = G[u][j];
            if (distance[v] == -1) {
                distance[v] = distance[u] + 1;
                prevTop[v] = u;
                Q.push(v);
            }
        }
    }

    //print results
    for (int i = 0; i < prevTop.size(); i++) {
        cout << i << '(' << distance[i] << ")\t:";
        int x = prevTop[i];
        while (x != -1) {
            cout << x << ' ';
            x = prevTop[x];
        }
        cout << endl;
    }

    return;
}

Задачи, решаемые с помощью поиска в ширину

Проверка графа на связность

Выполняется проще простого. Инициализируем массив distance и смотрим от всех ли вершин можно добраться до стартовой. Если хотя бы от одной вершины путь отсутствует — граф несвязен.

bool isConnected(graphNotWeighted &G, int start) {
    queue<int> Q;
    vector<int> distance(G.size(), -1);
    vector<int> prevTop(G.size(), -1);

    distance[start] = 0;
    Q.push(start);
    while (Q.size()) {
        int u = Q.front();
        Q.pop();
        for (int j = 0; j < G[u].size(); j++) {
            int v = G[u][j];
            if (distance[v] == -1) {
                distance[v] = distance[u] + 1;
                prevTop[v] = u;
                Q.push(v);
            }
        }
     }

    //print results
    for (int i = 0; i < G.size(); ++i)
        if (distance[i] == -1)
         return false;

    return true;
}

Подсчет количества компонент связности графа

Смысл в том, что после вызова процедуры BFS для вершины i , в массиве distance будут инициализированы все вершины из ее компоненты. Вызывая процедуру для каждой вершины, мы найдем все возможные компоненты связности.

unsigned int connectedComponentsCount(graphNotWeighted &G) {
    queue<int> Q;
    vector<int> distance(G.size(), -1);
    vector<int> prevTop(G.size(), -1);

    unsigned int count = 0;
    for(int start = 0; start < G.size(); start++) {
        if(distance[start] == -1) {
            distance[start] = 0;
            Q.push(start);
            while (Q.size()) {
                int u = Q.front();
                Q.pop();
                for (int j = 0; j < G[u].size(); j++) {
                    int v = G[u][j];
                    if (distance[v] == -1) {
                        distance[v] = distance[u] + 1;
                        prevTop[v] = u;
                        Q.push(v);
                    }
                }
            }

        count++;
        }
    }

    return count;
}