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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Использование обхода в глубину для поиска цикла)
Строка 1: Строка 1:
 
== Алгоритм проверки наличия пути между двумя вершинами ==
 
== Алгоритм проверки наличия пути между двумя вершинами ==
  
=== Задача ===
+
{{Задача
 
+
|definition =
 
Дан граф <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо проверить, существует ли путь из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.
 
Дан граф <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо проверить, существует ли путь из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.
 
+
}}
 
=== Алгоритм ===
 
=== Алгоритм ===
  
Строка 12: Строка 12:
 
=== Реализация ===
 
=== Реализация ===
  
  '''bool[]''' visited;                                //массив цветов вершин
+
  '''bool[]''' visited;                                <font color=green>//массив цветов вершин</font>
 
   
 
   
  '''bool''' dfs(u: '''int''')               
+
  '''bool''' dfs(u: '''int'''):              
     '''if''' (u == t)
+
     '''if''' u == t
 
         '''return''' ''true'';     
 
         '''return''' ''true'';     
     visited[u] = ''true'';                          //помечаем вершину как пройденную
+
     visited[u] = ''true'';                          <font color=green>//помечаем вершину как пройденную</font>
     '''for''' (v таких, что (u, v) — ребро в G)      //проходим по смежным с u вершинам
+
     '''for''' v таких, что (u, v) — ребро в G         <font color=green>//проходим по смежным с u вершинам</font>
         '''if''' ('''not''' visited[v])                    //проверяем, не находились ли мы ранее в выбранной вершине
+
         '''if''' '''not''' visited[v]                       <font color=green>//проверяем, не находились ли мы ранее в выбранной вершине</font>
             '''if''' (dfs(v))
+
             '''if''' dfs(v)
 
                 '''return''' ''true'';
 
                 '''return''' ''true'';
 
     '''return''' ''false'';
 
     '''return''' ''false'';
Строка 26: Строка 26:
 
== Алгоритм проверки связности графа G ==
 
== Алгоритм проверки связности графа G ==
  
=== Задача ===
+
{{Задача
 
+
|definition =
 
Дан [[Основные определения теории графов|неориентированный граф]] <tex>G</tex>. Необходимо проверить, является ли он связным.
 
Дан [[Основные определения теории графов|неориентированный граф]] <tex>G</tex>. Необходимо проверить, является ли он связным.
 +
}}
  
 
=== Алгоритм ===
 
=== Алгоритм ===
  
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре <code>dfs()</code> будем уменьшать счётчик на единицу при входе в процедуру. Запустим алгоритм от некоторой вершины нашего графа. Если в конце работы процедуры <code>dfs()</code> счётчик равен нулю, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за <tex>O(M + N)</tex>.
+
Заведём счётчик количества вершин, которые мы ещё не посетили. В стандартной процедуре <code>dfs()</code> будем уменьшать счётчик на единицу при входе в процедуру. Запустим алгоритм от некоторой вершины нашего графа. Если в конце работы процедуры <code>dfs()</code> счётчик равен нулю, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за <tex>O(M + N)</tex>.
  
 
=== Реализация ===
 
=== Реализация ===
  
  '''bool[]''' visited;                                //массив цветов вершин
+
  '''bool[]''' visited;                                <font color=green>//массив цветов вершин</font>
  '''int''' k = n;                                    //счетчик изначально равен количеству вершин
+
  '''int''' k = n;                                    <font color=green>//счетчик изначально равен количеству вершин</font>
 
   
 
   
  function dfs(u: '''int''')               
+
  function dfs(u: '''int'''):              
 
     k--;
 
     k--;
     visited[u] = ''true'';                        //помечаем вершину как пройденную
+
     visited[u] = ''true'';                        <font color=green>//помечаем вершину как пройденную</font>
     '''for''' (v таких, что (u, v) — ребро в G)      //проходим по смежным с u вершинам
+
     '''for''' v таких, что (u, v) — ребро в G       <font color=green>//проходим по смежным с u вершинам</font>
         '''if''' ('''not''' visited[v])                    //проверяем, не находились ли мы ранее в выбранной вершине
+
         '''if''' '''not''' visited[v]                     <font color=green>//проверяем, не находились ли мы ранее в выбранной вершине</font>
 
             dfs(v);
 
             dfs(v);
 +
 +
==Проверка связности вершин в режиме онлайн==
 +
{{Задача
 +
|definition =
 +
Дан пустой граф <tex>G</tex>, состоящий из <tex>n</tex> вершин. Поступают запросы, каждый из которых {{---}} это пара вершин, между которыми надо добавить ребро. Необходимо в любой момент времени для двух выбранных вершин отвечать на вопрос, являются ли они связанными.
 +
}}
 +
===Алгоритм===
 +
Описываемая здесь идея довольна проста и будет основываться на структуре данных [[СНМ (наивные реализации)|"система непересекающихся множеств"]].
 +
 +
В каждом множестве будем хранить компоненты связности графа <tex>G</tex>. Тогда ответ на запросы второго типа будет заключаться в определении множеств, в которых находятся данные вершины, т.е. две вершины являются связанными, если они лежат в одной компоненте связности. Изначально все вершины находятся в разных компонентах связности. При добавлении ребра объединяем множества, в которых находятся его концы, если те различны.
  
 
== См. также ==
 
== См. также ==
 
*[[Обход в глубину, цвета вершин]]
 
*[[Обход в глубину, цвета вершин]]
*[[Лемма о белых путях]]
 
 
*[[Использование обхода в глубину для поиска цикла]]
 
*[[Использование обхода в глубину для поиска цикла]]
 +
 +
== Источники информации ==
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обход в глубину]]
 
[[Категория: Обход в глубину]]

Версия 16:29, 18 октября 2015

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

Задача:
Дан граф [math]G[/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(M + N)[/math].

Реализация

bool[] visited;                                 //массив цветов вершин

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

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

Задача:
Дан неориентированный граф [math]G[/math]. Необходимо проверить, является ли он связным.


Алгоритм

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

Реализация

bool[] visited;                                //массив цветов вершин
int k = n;                                     //счетчик изначально равен количеству вершин

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

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

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

Алгоритм

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

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

См. также

Источники информации