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

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

{{Задача
|definition =
Дан граф <tex>G = (V, E)</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо проверить, существует ли путь из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.
}}
=== Алгоритм ===

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

=== Реализация ===

 <font color=green>// visited {{---}} массив цветов вершин</font> 
 <font color=green>// t {{---}} конечная вершина</font> 
 
 '''bool''' dfs(u, t: '''int''', visited: '''bool[]'''):             
     '''if''' u == t
         '''return''' ''true''    
     visited[u] = ''true''                              <font color=green>// помечаем вершину как пройденную</font>
     '''for''' v: uv <tex>\in</tex> E                                  <font color=green>// проходим по смежным с u вершинам</font>
         '''if''' '''not''' visited[v]                          <font color=green>// проверяем, не находились ли мы ранее в выбранной вершине</font>
             '''if''' dfs(v, t, visited)
                 '''return''' ''true''
     '''return''' ''false''

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

{{Задача
|definition =
Дан [[Основные определения теории графов|неориентированный граф]] <tex>G = (V, E)</tex>. Необходимо проверить, является ли он связным.
}}

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

=== Реализация ===

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

==Проверка связности вершин в режиме онлайн==
{{Задача
|definition =
Дан пустой граф <tex>G</tex>, состоящий из <tex>n</tex> вершин. Поступают запросы, каждый из которых {{---}} это пара вершин, между которыми надо добавить ребро. Необходимо в любой момент времени для двух выбранных вершин отвечать на вопрос, являются ли они связанными.
}}
===Алгоритм===
Описываемая здесь идея довольна проста и будет основываться на [[СНМ (наивные реализации)|системе непересекающихся множеств]]. 

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

== См. также ==
*[[Обход в глубину, цвета вершин]]
*[[Использование обхода в глубину для поиска цикла]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]