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