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