Изменения

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

Навигация