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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Изменена структура статьи, псевдокод отформатирован и раскрашен.)
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 4 участников)
Строка 1: Строка 1:
== Алгоритм проверки наличия пути из s в t ==
+
== Алгоритм проверки наличия пути между двумя вершинами ==
 
 
=== Задача ===
 
 
 
Дан граф <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо проверить, существует ли путь из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.
 
  
 +
{{Задача
 +
|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>s</tex> и проверять при каждом посещении вершины, не является ли она искомой вершиной <tex>t</tex>.
Так как в первый момент времени все пути в графе "белые", то если вершина <tex>t</tex> и была достижима из <tex>s</tex>, то по [[Лемма о белых путях|лемме о белых путях]] в какой-то момент времени мы зайдём в вершину <tex>t</tex>, чтобы её покрасить. Время работы алгоритма <tex>O(M + N)</tex>.
+
Так как в первый момент времени все пути в графе "белые", то если вершина <tex>t</tex> и была достижима из <tex>s</tex>, то по [[Лемма о белых путях|лемме о белых путях]] в какой-то момент времени мы зайдём в вершину <tex>t</tex>, чтобы её покрасить. Время работы алгоритма <tex>O(|V| + |E|)</tex>.
  
 
=== Реализация ===
 
=== Реализация ===
  
  vector<bool> visited;                            //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах
+
  <font color=green>// visited {{---}} массив цветов вершин</font>
 +
<font color=green>// t {{---}} конечная вершина</font>
 
   
 
   
  bool dfs(int u)            
+
  '''bool''' dfs(u, t: '''int''', visited: '''bool[]'''):           
{
+
     '''if''' u == t
     '''if''' (u == t)
+
         '''return''' ''true''    
         '''return''' true;    
+
     visited[u] = ''true''                              <font color=green>// помечаем вершину как пройденную</font>
     visited[u] = true;                            //помечаем вершину как пройденную
+
     '''for''' v: uv <tex>\in</tex> E                                  <font color=green>// проходим по смежным с u вершинам</font>
     '''for''' (v таких, что (u, v) — ребро в G)  //проходим по смежным с u вершинам
+
         '''if''' '''not''' visited[v]                         <font color=green>// проверяем, не находились ли мы ранее в выбранной вершине</font>
         '''if''' (!visited[v])                    //проверяем, не находились ли мы ранее в выбранной вершине
+
             '''if''' dfs(v, t, visited)
             '''if''' (dfs(v))
+
                 '''return''' ''true''
                 '''return''' true;
+
     '''return''' ''false''
    '''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 ==
  
=== Задача ===
+
{{Задача
 +
|definition =
 +
Дан [[Основные определения теории графов|неориентированный граф]] <tex>G = (V, E)</tex>. Необходимо проверить, является ли он связным.
 +
}}
 +
 
 +
=== Алгоритм ===
 +
Снова небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]], в которой будем возвращать количество посещенных вершин. Запустим такой <code>dfs()</code> от некоторой вершины графа <tex>G</tex>, если его результат равен <tex>|V|</tex>, то мы побывали во всех вершинах графа, а следовательно он связен, иначе какие-то вершины остались непосещенными. Работает алгоритм за <tex>O(|V| + |E|)</tex>.
  
Дан [[Основные определения теории графов|неориентированный граф]] <tex>G</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
  
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу при входе в процедуру. Запустимся от какой-то вершины нашего графа. Если в конце работы процедуры dfs() счётчик равен нулю, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за <tex>O(M + N)</tex>.
+
==Проверка связности вершин в режиме онлайн==
 +
{{Задача
 +
|definition =
 +
Дан пустой граф <tex>G</tex>, состоящий из <tex>n</tex> вершин. Поступают запросы, каждый из которых {{---}} это пара вершин, между которыми надо добавить ребро. Необходимо в любой момент времени для двух выбранных вершин отвечать на вопрос, являются ли они связанными.
 +
}}
 +
===Алгоритм===
 +
Описываемая здесь идея довольна проста и будет основываться на [[СНМ (наивные реализации)|системе непересекающихся множеств]].  
  
=== Реализация ===
+
В каждом множестве будем хранить компоненты связности графа <tex>G</tex>. Тогда ответ на запросы второго типа будет заключаться в определении множеств, в которых находятся данные вершины, т.е. две вершины являются связанными, если они лежат в одной компоненте связности. Изначально все вершины находятся в разных компонентах связности. При добавлении ребра объединяем множества, в которых находятся его концы, если те различны.
  
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);                    //в начале все вершины в графе ''не пройденные''
 
    k = n;
 
    '''for''' (int i = 0; i < n; i++)
 
        dfs(i);
 
    '''if''' (k == 0)
 
        std::out << "Граф связен";                //вывести, что граф связен
 
    '''else''' 
 
        std::out << "Граф несвязен";              //вывести, что граф несвязен
 
    '''return''' 0;
 
}
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обход в глубину]]
 
[[Категория: Обход в глубину]]

Текущая версия на 19:17, 4 сентября 2022

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

Задача:
Дан граф [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]. Тогда ответ на запросы второго типа будет заключаться в определении множеств, в которых находятся данные вершины, т.е. две вершины являются связанными, если они лежат в одной компоненте связности. Изначально все вершины находятся в разных компонентах связности. При добавлении ребра объединяем множества, в которых находятся его концы, если те различны.

См. также