68
правок
Изменения
Нет описания правки
== Алгоритм проверки наличия пути из S в T между двумя вершинами ==* '''Задача'''Дан граф G и две вершины S и T. Необходимо проверить существует ли путь из вершины S в вершину T по рёбрам графа G.
'''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;===Алгоритм=== }Описываемая здесь идея довольна проста и будет основываться на [[СНМ (наивные реализации)|системе непересекающихся множеств]].
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]