Использование обхода в глубину для проверки связности

Алгоритм проверки наличия пути из S в T

• Задача

Дан граф G и две вершины S и T. Необходимо проверить существует ли путь из вершины S в вершину T по рёбрам графа G.

• Алгоритм

Небольшая модификация алгоритма обхода в глубину. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины S и проверять при каждом посещении вершины, не является ли она искомой вершиной T. Так как в первый момент времени все пути в графе "белые", то если вершина T и была достижима из S, то по Лемме о белых путях в какой-то момент времени мы зайдём в вершину T, чтобы её покрасить. Время работы алгоритма O(M + N).

• Реализация

vector<bool> visited;                       //вектор для хранения информации о пройденных и не пройденных вершинах

bool dfs(int u)              
{
    if(u == t)
        return true;    
    visited[u] = true;                      //помечаем вершину как пройденную
    for (v таких, что (u, v) - ребро в G)   //проходим по смежным с u вершинам
        if (!visited[v])                    //проверяем, не находились ли мы ранее в выбранной вершине
            if(dfs(v))
                return true;
    return false;
}

int main()
{
    ...                                     //задание графа G с количеством вершин n и вершин S и T.
    visited.assign(n, false);               //в начале все вершины в графе не пройденные
    if(dfs(s))
         std::out << "Путь из S в T существует";
       else 
         std::out << "Пути из S в T нет";
    return 0;
}

Алгоритм проверки связности ВСЕГО графа G

• Задача

Дан неориентированный граф G. Необходимо проверить является ли он связным.

• Алгоритм

Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу перед выходом из процедуры. Запустимся от какой-то вершины нашего графа. По окончании работы процедуры dfs() сравним счётчик с нулём. Если они равны, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за O(M + N).

• Реализация

vector<bool> visited;                       //вектор для хранения информации о пройденных и не пройденных вершинах
int k = 0;

void dfs(int u)              
{
    k--;
    visited[u] = true;                      //помечаем вершину как пройденную
    for (v таких, что (u, v) - ребро в G)   //проходим по смежным с u вершинам
        if (!visited[v])                    //проверяем, не находились ли мы ранее в выбранной вершине
            dfs(v);
}

int main()
{
    ...                                     //задание графа G с количеством вершин n и вершин S и T.
    visited.assign(n, false);               //в начале все вершины в графе не пройденные
    int k = n;
    for(int i = 0; i < n; i++)
        dfs(i);
    if(k == 0)
        std::out << "Граф связен";          //вывести, что граф связен
      else
        std::out << "Граф несвязен";        //вывести, что граф несвязен
    return 0;
}