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