Изменения

== Задача Алгоритм проверки наличия пути между двумя вершинами ==Дан [[Основные определения теории графов|неориентированный граф]] G и две вершины U и V. Необходимо проверить существует ли путь из вершины U в вершину V по рёбрам графа G.

{{Задача|definition =Дан граф <tex>G = (V, E)</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо проверить, существует ли путь из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.}}=== Алгоритм === Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины U <tex>s</tex> и проверять при каждом посещении вершины, не является ли она искомой вершиной V<tex>t</tex>.Так как в первый момент времени все пути в графе "белые", то если вершина V <tex>t</tex> и была достижима из U<tex>s</tex>, то по [[Лемма о белых путях|Лемме лемме о белых путях]] в какой-то момент времени мы зайдём в вершину V<tex>t</tex>, чтобы её покрасить. Время работы алгоритма <tex>O(M |V| + N|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) retrun '''return''' ''true;'' '''return ''' ''false;'' } == Алгоритм проверки связности графа G == int main() {{Задача|definition = ... //задание графа Дан [[Основные определения теории графов|неориентированный граф]] <tex>G с количеством вершин n и вершин S и T. visited.assign= (nV, falseE); <//в начале все вершины в графе ''не пройденные''tex>. Необходимо проверить, является ли он связным. if(dfs(s)) std::out << "Путь из S в T существует"; else std::out << "Пути из S в T нет"; return 0; }}

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

void <font color=green>// visited {{---}} массив цветов вершин</font> '''int''' dfs(u: '''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В каждом множестве будем хранить компоненты связности графа <tex>G</tex>. Тогда ответ на запросы второго типа будет заключаться в определении множеств, в которых находятся данные вершины, т.е.assign(nдве вершины являются связанными, false); //если они лежат в начале одной компоненте связности. Изначально все вершины находятся в графе ''не пройденные''разных компонентах связности. При добавлении ребра объединяем множества, в которых находятся его концы, если те различны.  int k = n; for(int i = 0; i < n; i++) dfs(i); if(k См. также == 0) //вывести*[[Обход в глубину, что граф связенцвета вершин]] else //вывести, что граф несвязен return 0; }*[[Использование обхода в глубину для поиска цикла]]