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

Алгоритм проверки наличия пути между двумя вершинами

Задача:

Дан граф [math]G = (V, E)[/math] и две вершины [math]s[/math] и [math]t[/math]. Необходимо проверить, существует ли путь из вершины [math]s[/math] в вершину [math]t[/math] по рёбрам графа [math]G[/math].

Алгоритм

Небольшая модификация алгоритма обхода в глубину. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины [math]s[/math] и проверять при каждом посещении вершины, не является ли она искомой вершиной [math]t[/math]. Так как в первый момент времени все пути в графе "белые", то если вершина [math]t[/math] и была достижима из [math]s[/math], то по лемме о белых путях в какой-то момент времени мы зайдём в вершину [math]t[/math], чтобы её покрасить. Время работы алгоритма [math]O(|V| + |E|)[/math].

Реализация

// visited — массив цветов вершин 
// t — конечная вершина 

bool dfs(u, t: int, visited: bool[]):             
    if u == t
        return true    
    visited[u] = true                              // помечаем вершину как пройденную
    for v: uv [math]\in[/math] E                                  // проходим по смежным с u вершинам
        if not visited[v]                          // проверяем, не находились ли мы ранее в выбранной вершине
            if dfs(v, t, visited)
                return true
    return false

Алгоритм проверки связности графа G

Задача:

Дан неориентированный граф [math]G = (V, E)[/math]. Необходимо проверить, является ли он связным.

Алгоритм

Снова небольшая модификация алгоритма обхода в глубину, в которой будем возвращать количество посещенных вершин. Запустим такой dfs() от некоторой вершины графа [math]G[/math], если его результат равен [math]|V|[/math], то мы побывали во всех вершинах графа, а следовательно он связен, иначе какие-то вершины остались непосещенными. Работает алгоритм за [math]O(|V| + |E|)[/math].

Реализация

// visited — массив цветов вершин  
                             
int dfs(u: int, visited: bool[]):              
    int visitedVertices = 1
    visited[u] = true                           // помечаем вершину как пройденную
    for v: uv [math]\in[/math] E                               // проходим по смежным с u вершинам
        if not visited[v]                       // проверяем, не находились ли мы ранее в выбранной вершине
            visitedVertices += dfs(v, visited)
    return visitedVertices

Проверка связности вершин в режиме онлайн

Задача:

Дан пустой граф [math]G[/math], состоящий из [math]n[/math] вершин. Поступают запросы, каждый из которых — это пара вершин, между которыми надо добавить ребро. Необходимо в любой момент времени для двух выбранных вершин отвечать на вопрос, являются ли они связанными.

Алгоритм

Описываемая здесь идея довольна проста и будет основываться на системе непересекающихся множеств.

В каждом множестве будем хранить компоненты связности графа [math]G[/math]. Тогда ответ на запросы второго типа будет заключаться в определении множеств, в которых находятся данные вершины, т.е. две вершины являются связанными, если они лежат в одной компоненте связности. Изначально все вершины находятся в разных компонентах связности. При добавлении ребра объединяем множества, в которых находятся его концы, если те различны.

См. также

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