Изменения

== Алгоритм проверки наличия пути из одной вершины в другую между двумя вершинами == === Задача === Дан граф <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо проверить, существует ли путь из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</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'';

=== {{Задача |definition =Дан [[Основные определения теории графов|неориентированный граф]] <tex>G ==(V, E)</tex>. Необходимо проверить, является ли он связным.}}

Дан === Алгоритм ===Снова небольшая модификация алгоритма [[Основные определения теории графовОбход в глубину, цвета вершин|неориентированный графобхода в глубину]] , в которой будем возвращать количество посещенных вершин. Запустим такой <code>dfs()</code> от некоторой вершины графа <tex>G</tex>. Необходимо проверить, является ли если его результат равен <tex>|V|</tex>, то мы побывали во всех вершинах графа, а следовательно он связнымсвязен, иначе какие-то вершины остались непосещенными. Работает алгоритм за <tex>O(|V| + |E|)</tex>.

=== Алгоритм Реализация ===

Заведём счётчик количества <font color=green>// visited {{---}} массив цветов вершин которые мы ещё не посетили. В стандартной процедуре <code/font> '''int''' dfs(u: '''int''', visited: '''bool[]'''): '''int''' visitedVertices = 1 visited[u] = ''true'' <font color=green>/code/ помечаем вершину как пройденную</font> '''for''' v: uv <tex>\in</tex> будем уменьшать счётчик на единицу при входе в процедуру. Запустим алгоритм от некоторой вершины нашего графа. Если в конце работы процедуры E <codefont color=green>dfs()// проходим по смежным с u вершинам</codefont> '''if''' '''not''' visited[v] <font color=green> счётчик равен нулю// проверяем, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то не находились ли мы не побывали ранее в какой-то выбранной вершине графа. Работает алгоритм за <tex/font>O visitedVertices += dfs(M + Nv, visited)</tex>. '''return''' visitedVertices

==Проверка связности вершин в режиме онлайн= Реализация ={{Задача|definition =Дан пустой граф <tex>G</tex>, состоящий из <tex>n</tex> вершин. Поступают запросы, каждый из которых {{---}} это пара вершин, между которыми надо добавить ребро. Необходимо в любой момент времени для двух выбранных вершин отвечать на вопрос, являются ли они связанными.}}===Алгоритм===Описываемая здесь идея довольна проста и будет основываться на [[СНМ (наивные реализации)|системе непересекающихся множеств]].

'''bool[]''' visited; В каждом множестве будем хранить компоненты связности графа <tex>G<//массив цветов вершин '''int''' k = n; //счетчик изначально равен количеству вершин function dfs(u: '''int''') k--; visited[u] = ''true''; //помечаем вершину как пройденную '''for''' (v такихtex>. Тогда ответ на запросы второго типа будет заключаться в определении множеств, в которых находятся данные вершины, что (uт.е. две вершины являются связанными, v) — ребро если они лежат в одной компоненте связности. Изначально все вершины находятся в G) //проходим по смежным с u вершинам '''if''' ('''not''' visited[v]) //проверяемразных компонентах связности. При добавлении ребра объединяем множества, не находились ли мы ранее в выбранной вершине dfs(v);которых находятся его концы, если те различны.

*[[Лемма о белых путях]]*[[Использование обхода в глубину для поиска цикла в ориентированном графе]]