Изменения

== Алгоритм проверки наличия пути из S в T между двумя вершинами ==* '''Задача'''Дан граф G и две вершины S и T. Необходимо проверить существует ли путь из вершины S в вершину T по рёбрам графа G.

* '''Алгоритм'''{{ЗадачаНебольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в томdefinition =Дан граф <tex>G = (V, чтобы запустить обход в глубину из E)</tex> и две вершины S <tex>s</tex> и проверять при каждом посещении вершины<tex>t</tex>. Необходимо проверить, не является существует ли она искомой вершиной T.Так как в первый момент времени все пути в графе "белые", то если вершина T и была достижима путь из S, то по [[Лемма о белых путях|лемме о белых путях]] в какой-то момент времени мы зайдём вершины <tex>s</tex> в вершину T, чтобы её покрасить. Время работы алгоритма O(M + N)<tex>t</tex> по рёбрам графа <tex>G</tex>.}}=== Алгоритм ===

* '''Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины <tex>s</tex> и проверять при каждом посещении вершины, не является ли она искомой вершиной <tex>t</tex>.Так как в первый момент времени все пути в графе "белые", то если вершина <tex>t</tex> и была достижима из <tex>s</tex>, то по [[Лемма о белых путях|лемме о белых путях]] в какой-то момент времени мы зайдём в вершину <tex>t</tex>, чтобы её покрасить. Время работы алгоритма <tex>O(|V| + |E|)</tex>. === Реализация'''===  vector<boolfont color=green> // visited; {{---}} массив цветов вершин</font> <font color=green>/вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах/ t {{---}} конечная вершина</font>

'''bool ''' dfs(u, t: '''int u''', 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 == int main() {{Задача|definition = Дан [[Основные определения теории графов|неориентированный граф]] <tex>G = (V, E)</tex>.Необходимо проверить, является ли он связным.}} === Алгоритм ===Снова небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]], в которой будем возвращать количество посещенных вершин. Запустим такой <code>dfs()</code> от некоторой вершины графа <tex>G</задание tex>, если его результат равен <tex>|V|</tex>, то мы побывали во всех вершинах графа G с количеством вершин n и вершин S и T, а следовательно он связен, иначе какие-то вершины остались непосещенными. Работает алгоритм за <tex>O(|V| + |E|)</tex>. === Реализация ===  <font color=green>// visited.assign{{---}} массив цветов вершин</font> '''int''' dfs(nu: '''int''', falsevisited: '''bool[]'''); : '''int''' visitedVertices = 1 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> visitedVertices += dfs(s)v, visited) std::out '''return''' visitedVertices ==Проверка связности вершин в режиме онлайн=={{Задача|definition =Дан пустой граф <tex>G< "Путь /tex>, состоящий из S в T существует"; else std::out <tex>n< "Пути /tex> вершин. Поступают запросы, каждый из S которых {{---}} это пара вершин, между которыми надо добавить ребро. Необходимо в T нет";любой момент времени для двух выбранных вершин отвечать на вопрос, являются ли они связанными.}} return 0;===Алгоритм=== }Описываемая здесь идея довольна проста и будет основываться на [[СНМ (наивные реализации)|системе непересекающихся множеств]].

== Алгоритм проверки В каждом множестве будем хранить компоненты связности ВСЕГО графа <tex>G ==* '''Задача'''Дан [[Основные определения теории графов|неориентированный граф]] G</tex>. Необходимо проверить является ли он связным.* '''Алгоритм'''Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик Тогда ответ на единицу перед выходом из процедуры. Запустимся от какой-то запросы второго типа будет заключаться в определении множеств, в которых находятся данные вершины нашего графа, т. По окончании работы процедуры dfs() сравним счётчик с нулёме. Если две вершины являются связанными, если они равны, то мы побывали во всех вершинах графа, а следовательно он связенлежат в одной компоненте связности. Изначально все вершины находятся в разных компонентах связности. Если счётчик отличен от нуляПри добавлении ребра объединяем множества, то мы не побывали в какой-то вершине графа. Работает алгоритм за O(M + N)которых находятся его концы, если те различны.

* '''Реализация''' vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах int k = 0;= См. также == void dfs(int u) { k--; visited*[[u] = true; //помечаем вершину как пройденную for (v таких, что (u, v) - ребро Обход в G) //проходим по смежным с u вершинам if (!visited[v]) //проверяемглубину, не находились ли мы ранее в выбранной вершине dfs(v); } int main() { ... //задание графа G с количеством цвета вершин n и вершин S и T.]] visited.assign(n, false); //*[[Использование обхода в начале все вершины в графе ''не пройденные'' int k = n; for(int i = 0; i < n; i++) dfs(i); if(k == 0) std::out << "Граф связен"; //вывести, что граф связен else std::out << "Граф несвязен"; //вывести, что граф несвязен return 0; }глубину для поиска цикла]]