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