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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлен случай неориентированности)
(Реализация для случая ориентированного графа)
(не показано 7 промежуточных версий 2 участников)
Строка 1: Строка 1:
Пусть дан без петель и кратных рёбер. Требуется проверить наличие [[Основные определения теории графов|цикла]] в этом графе.
+
{{Задача
 +
|definition = Дан граф, требуется проверить наличие [[Основные определения теории графов|цикла]] в этом графе.
 +
}}
  
Решим эту задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]] за <tex>O(M)</tex>.
+
== Алгоритм ==
  
== Алгоритм ==
+
Будем решать задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]].
  
Пусть дан <b>ориентированный граф</b>. Произведём серию поисков в глубину в графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе {{---}} в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл.
+
В случае <b>ориентированного графа</b> произведём серию обходов. То есть из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе из нее {{---}} в чёрный. И, если алгоритм пытается пойти в серую вершину, то это означает, что цикл найден.
  
В случае <b>неориентированного графа</b> любое ребро представляется как два ребра {{---}} прямое и обратное. Тогда мы посчитаем, что эти два ребра составляют цикл, что неверно. Чтобы избежать этого, будем передавать еще один параметр поиска в глубину {{---}} вершину, из которой мы пришли. Теперь мы считаем, что нашли цикл, если вершина, в которую мы хотим пойти серая и не является вершиной из которой мы пришли.
+
В случае <b>неориентированного графа</b>, одно ребро не должно встречаться в [[Основные определения теории графов#def_no_graph_path|цикле]] дважды по определению. Поэтому необходимо дополнительно проверять, что текущее рассматриваемое из вершины ребро не являетя тем ребром, по которому мы пришли в эту вершину.
  
Для восстановления самого цикла достаточно при запуске поиска в глубину из очередной вершины добавлять эту вершину в стек. Когда поиск в глубину нашел вершину, которая лежит на цикле, будем последовательно вынимать вершины из стека, пока не встретим найденную еще раз. Все вынутые вершины будут лежать на искомом цикле.
+
Заметим, что, если в графе есть вершины с петлями, то алгоритм будет работать корректно, так как при запуске поиска в глубину из такой вершины, найдется ребро, ведущее в нее же, а значит эта петля и будет являться циклом.
[[Файл: Dfs_cycle.png|thumb|200px|right| Момент нахождения цикла: синие ребра {{---}} уже пройденные, красное ребро ведет в серую, уже пройденную, вершину.]]
 
  
== Доказательство ==
+
Для восстановления самого цикла достаточно при запуске поиска в глубину из очередной вершины добавлять эту вершину в [[Стек|стек]]. Когда поиск в глубину нашел вершину, которая лежит на цикле, будем последовательно вынимать вершины из стека, пока не встретим найденную еще раз. Все вынутые вершины будут лежать на искомом цикле.
  
Пусть дан граф <tex>G</tex>. Запустим <tex>dfs(G)</tex>. Рассмотрим выполнение процедуры поиска в глубину от некоторой вершины <tex> v </tex>. Так как все серые вершины лежат в стеке рекурсии, то для них вершина <tex> v </tex> достижима, так как между соседними вершинами в стеке есть ребро. Тогда если из рассматриваемой вершины <tex> v </tex> существует ребро в серую вершину <tex> u </tex>, то это значит, что из вершины <tex> u </tex> существует путь в <tex> v </tex> и из вершины <tex> v </tex> существует путь в <tex> u </tex> состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существует.
+
Асимптотика поиска цикла совпадает с асимптотикой поиска в глубину {{---}} <tex>O(|V| + |E|)</tex>.
  
Докажем, что если в графе <tex>G</tex> существует цикл, то <tex>dfs(G)</tex> его всегда найдет. Пусть <tex> v </tex> {{---}} первая вершина принадлежащая циклу, рассмотренная поиском в глубину. Тогда существует вершина <tex> u </tex>, принадлежащая циклу и имеющая ребро в вершину <tex> v </tex>. Так как из вершины <tex> v </tex> в вершину <tex> u </tex> существует белый путь (они лежат на одном цикле), то по [[Лемма о белых путях|лемме о белых путях]] во время выполнения процедуры поиска в глубину от вершины <tex> u </tex>, вершина <tex> v </tex> будет серой. Так как из <tex> u </tex> есть ребро в <tex> v </tex>, то это ребро в серую вершину. Следовательно <tex>dfs(G)</tex> нашел цикл.
+
[[Файл: Dfs_cycle.png|thumb|200px|right| Момент нахождения цикла: <font color=blue>синие</font> ребра {{---}} уже пройденные, <font color=red>красное</font> ребро ведет в серую, уже пройденную, вершину.]]
  
== Реализация для случая ориентированного графа ==
+
== Доказательство ==
  
'''int''' graph[][];
+
Пусть дан граф <tex>G</tex>. Запустим <tex>\mathrm{dfs}(G)</tex>. Рассмотрим выполнение процедуры поиска в глубину от некоторой вершины <tex> v </tex>. Так как все серые вершины лежат в стеке рекурсии, то для них вершина <tex> v </tex> достижима, так как между соседними вершинами в стеке есть ребро. Тогда, если из рассматриваемой вершины <tex> v </tex> существует ребро в серую вершину <tex> u </tex>, то это значит, что из вершины <tex> u </tex> существует путь в <tex> v </tex> и из вершины <tex> v </tex> существует путь в <tex> u </tex> состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существует.
'''int''' color[] <tex> \leftarrow </tex> white; <font color=darkgreen> // Массив цветов, изначально все вершины белые </font>
 
  
'''func''' dfs(u: '''int'''):          <font color=darkgreen> // u {{---}} вершина, в которой мы сейчас находимся </font>
+
Докажем, что если в графе <tex>G</tex> существует цикл, то <tex>\mathrm{dfs}(G)</tex> его всегда найдет. Пусть <tex> v </tex> {{---}} первая вершина принадлежащая циклу, рассмотренная поиском в глубину. Тогда существует вершина <tex> u </tex>, принадлежащая циклу и имеющая ребро в вершину <tex> v </tex>. Так как из вершины <tex> v </tex> в вершину <tex> u </tex> существует белый путь (они лежат на одном цикле), то по [[Лемма о белых путях|лемме о белых путях]] во время выполнения процедуры поиска в глубину от вершины <tex> u </tex>, вершина <tex> v </tex> будет серой. Так как из <tex> u </tex> есть ребро в <tex> v </tex>, то это ребро в серую вершину. Следовательно <tex>\mathrm{dfs}(G)</tex> нашел цикл.
    color[u] = grey;             
 
    '''for''' (v : uv {{---}} edge)
 
        if (color[v] == white)
 
            dfs(v);
 
        if (color[v] == grey)
 
            print();            <font color=darkgreen> // вывод ответа </font>  
 
    color[u] = black;       
 
  
== Реализация для случая неориентированного графа ==
+
== Реализация для случая ориентированного графа ==
 +
<font color=darkgreen>// color {{---}} массив цветов, изначально все вершины белые </font>
 +
'''func''' dfs(v: '''vertex'''):            <font color=darkgreen> // v {{---}} вершина, в которой мы сейчас находимся </font>
 +
    color[v] = <i>grey</i>           
 +
    '''for''' (u: vu <tex>\in</tex> E)
 +
        '''if''' (color[u] == <i>white</i>)
 +
            dfs(u)
 +
        '''if''' (color[u] == <i>grey</i>)
 +
            print()            <font color=darkgreen> // вывод ответа </font> 
 +
    color[v] = <i>black</i>
  
'''int''' graph[][];
+
== См. также ==
'''int''' color[] <tex> \leftarrow </tex> white; <font color=darkgreen> // Массив цветов, изначально все вершины белые </font>
+
* [[Использование обхода в глубину для проверки связности]]
 +
* [[Использование обхода в глубину для топологической сортировки]]
 +
* [[Использование обхода в глубину для поиска компонент сильной связности]]
 +
* [[Использование обхода в глубину для поиска точек сочленения]]
 +
* [[Использование обхода в глубину для поиска мостов]]
  
'''func''' dfs(u, par: '''int'''): <font color=darkgreen> // u {{---}} вершина, в которой мы сейчас находимся; par {{---}} вершина, из которой мы пришли в u </font>
 
    color[u] = grey;           
 
    '''for''' (v : uv {{---}} edge)
 
        if (color[v] == white)
 
            dfs(v, u);
 
        if (color[v] == grey '''and''' v <tex>\neq</tex> par)
 
            print();            <font color=darkgreen> // вывод ответа </font> 
 
    color[u] = black;       
 
 
== Источники информации ==
 
== Источники информации ==
 
* [http://e-maxx.ru/algo/finding_cycle MAXimal :: algo {{---}} «Проверка графа на ацикличность и нахождение цикла»]
 
* [http://e-maxx.ru/algo/finding_cycle MAXimal :: algo {{---}} «Проверка графа на ацикличность и нахождение цикла»]
 
* [http://shujkova.ru/sites/default/files/algorithm2.pdf Прикладные задачи алгоритма DFS]
 
* [http://shujkova.ru/sites/default/files/algorithm2.pdf Прикладные задачи алгоритма DFS]
 
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
 
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обход в глубину]]
 
[[Категория: Обход в глубину]]

Версия 00:41, 21 июня 2018

Задача:
Дан граф, требуется проверить наличие цикла в этом графе.


Алгоритм

Будем решать задачу с помощью поиска в глубину.

В случае ориентированного графа произведём серию обходов. То есть из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе из нее — в чёрный. И, если алгоритм пытается пойти в серую вершину, то это означает, что цикл найден.

В случае неориентированного графа, одно ребро не должно встречаться в цикле дважды по определению. Поэтому необходимо дополнительно проверять, что текущее рассматриваемое из вершины ребро не являетя тем ребром, по которому мы пришли в эту вершину.

Заметим, что, если в графе есть вершины с петлями, то алгоритм будет работать корректно, так как при запуске поиска в глубину из такой вершины, найдется ребро, ведущее в нее же, а значит эта петля и будет являться циклом.

Для восстановления самого цикла достаточно при запуске поиска в глубину из очередной вершины добавлять эту вершину в стек. Когда поиск в глубину нашел вершину, которая лежит на цикле, будем последовательно вынимать вершины из стека, пока не встретим найденную еще раз. Все вынутые вершины будут лежать на искомом цикле.

Асимптотика поиска цикла совпадает с асимптотикой поиска в глубину — [math]O(|V| + |E|)[/math].

Момент нахождения цикла: синие ребра — уже пройденные, красное ребро ведет в серую, уже пройденную, вершину.

Доказательство

Пусть дан граф [math]G[/math]. Запустим [math]\mathrm{dfs}(G)[/math]. Рассмотрим выполнение процедуры поиска в глубину от некоторой вершины [math] v [/math]. Так как все серые вершины лежат в стеке рекурсии, то для них вершина [math] v [/math] достижима, так как между соседними вершинами в стеке есть ребро. Тогда, если из рассматриваемой вершины [math] v [/math] существует ребро в серую вершину [math] u [/math], то это значит, что из вершины [math] u [/math] существует путь в [math] v [/math] и из вершины [math] v [/math] существует путь в [math] u [/math] состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существует.

Докажем, что если в графе [math]G[/math] существует цикл, то [math]\mathrm{dfs}(G)[/math] его всегда найдет. Пусть [math] v [/math] — первая вершина принадлежащая циклу, рассмотренная поиском в глубину. Тогда существует вершина [math] u [/math], принадлежащая циклу и имеющая ребро в вершину [math] v [/math]. Так как из вершины [math] v [/math] в вершину [math] u [/math] существует белый путь (они лежат на одном цикле), то по лемме о белых путях во время выполнения процедуры поиска в глубину от вершины [math] u [/math], вершина [math] v [/math] будет серой. Так как из [math] u [/math] есть ребро в [math] v [/math], то это ребро в серую вершину. Следовательно [math]\mathrm{dfs}(G)[/math] нашел цикл.

Реализация для случая ориентированного графа

// color — массив цветов, изначально все вершины белые  
func dfs(v: vertex):             // v — вершина, в которой мы сейчас находимся 
    color[v] = grey             
    for (u: vu [math]\in[/math] E)
        if (color[u] == white)
            dfs(u)
        if (color[u] == grey)
            print()              // вывод ответа    
    color[v] = black

См. также

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