68
правок
Изменения
Нет описания правки
{{Задача
|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''' 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>. Необходимо проверить, является ли он связным.
}}
=== Алгоритм ===
=== Реализация ===
==Проверка связности вершин в режиме онлайн==
}}
===Алгоритм===
Описываемая здесь идея довольна проста и будет основываться на структуре данных [[СНМ (наивные реализации)|"система системе непересекающихся множеств"]].
В каждом множестве будем хранить компоненты связности графа <tex>G</tex>. Тогда ответ на запросы второго типа будет заключаться в определении множеств, в которых находятся данные вершины, т.е. две вершины являются связанными, если они лежат в одной компоненте связности. Изначально все вершины находятся в разных компонентах связности. При добавлении ребра объединяем множества, в которых находятся его концы, если те различны.
*[[Обход в глубину, цвета вершин]]
*[[Использование обхода в глубину для поиска цикла]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
