68
правок
Изменения
Нет описания правки
== Алгоритм проверки наличия пути из s в t между двумя вершинами == === Задача === Дан граф <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо проверить, существует ли путь из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.
{{Задача
|definition =
Дан граф <tex>G = (V, E)</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо проверить, существует ли путь из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.
}}
=== Алгоритм ===
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины <tex>s</tex> и проверять при каждом посещении вершины, не является ли она искомой вершиной <tex>t</tex>.
Так как в первый момент времени все пути в графе "белые", то если вершина <tex>t</tex> и была достижима из <tex>s</tex>, то по [[Лемма о белых путях|лемме о белых путях]] в какой-то момент времени мы зайдём в вершину <tex>t</tex>, чтобы её покрасить. Время работы алгоритма <tex>O(M |V| + N|E|)</tex>.
=== Реализация ===
'''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'';
== Алгоритм проверки связности графа 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''' '''not''' visited[v] <font color=green>// проверяем, не находились ли мы ранее в выбранной вершине</font> visitedVertices += dfs(v, visited) '''return''' visitedVertices
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]