Использование обхода в глубину для проверки связности — различия между версиями
Kasetkin (обсуждение | вклад) (→Идея) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 33 промежуточные версии 7 участников) | |||
Строка 1: | Строка 1: | ||
− | == | + | == Алгоритм проверки наличия пути между двумя вершинами == |
− | |||
− | == | + | {{Задача |
− | + | |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(|V| + |E|)</tex>. | |
− | == | + | === Реализация === |
− | + | ||
− | + | <font color=green>// visited {{---}} массив цветов вершин</font> | |
− | + | <font color=green>// t {{---}} конечная вершина</font> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''bool''' dfs(u, t: '''int''', visited: '''bool[]'''): | |
− | for | + | '''if''' u == t |
− | + | '''return''' ''true'' | |
− | + | 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> | |
+ | '''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 | ||
+ | |||
+ | ==Проверка связности вершин в режиме онлайн== | ||
+ | {{Задача | ||
+ | |definition = | ||
+ | Дан пустой граф <tex>G</tex>, состоящий из <tex>n</tex> вершин. Поступают запросы, каждый из которых {{---}} это пара вершин, между которыми надо добавить ребро. Необходимо в любой момент времени для двух выбранных вершин отвечать на вопрос, являются ли они связанными. | ||
+ | }} | ||
+ | ===Алгоритм=== | ||
+ | Описываемая здесь идея довольна проста и будет основываться на [[СНМ (наивные реализации)|системе непересекающихся множеств]]. | ||
+ | |||
+ | В каждом множестве будем хранить компоненты связности графа <tex>G</tex>. Тогда ответ на запросы второго типа будет заключаться в определении множеств, в которых находятся данные вершины, т.е. две вершины являются связанными, если они лежат в одной компоненте связности. Изначально все вершины находятся в разных компонентах связности. При добавлении ребра объединяем множества, в которых находятся его концы, если те различны. | ||
+ | |||
+ | == См. также == | ||
+ | *[[Обход в глубину, цвета вершин]] | ||
+ | *[[Использование обхода в глубину для поиска цикла]] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Обход в глубину]] | [[Категория: Обход в глубину]] |
Текущая версия на 19:17, 4 сентября 2022
Алгоритм проверки наличия пути между двумя вершинами
Задача: |
Дан граф | и две вершины и . Необходимо проверить, существует ли путь из вершины в вершину по рёбрам графа .
Алгоритм
Небольшая модификация алгоритма обхода в глубину. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины и проверять при каждом посещении вершины, не является ли она искомой вершиной . Так как в первый момент времени все пути в графе "белые", то если вершина и была достижима из , то по лемме о белых путях в какой-то момент времени мы зайдём в вершину , чтобы её покрасить. Время работы алгоритма .
Реализация
// visited — массив цветов вершин
// t — конечная вершина
bool dfs(u, t: int, visited: bool[]):
if u == t
return true
visited[u] = true // помечаем вершину как пройденную
for v: uv
E // проходим по смежным с u вершинам
if not visited[v] // проверяем, не находились ли мы ранее в выбранной вершине
if dfs(v, t, visited)
return true
return false
Алгоритм проверки связности графа G
Задача: |
Дан неориентированный граф . Необходимо проверить, является ли он связным. |
Алгоритм
Снова небольшая модификация алгоритма обхода в глубину, в которой будем возвращать количество посещенных вершин. Запустим такой dfs()
от некоторой вершины графа , если его результат равен , то мы побывали во всех вершинах графа, а следовательно он связен, иначе какие-то вершины остались непосещенными. Работает алгоритм за .
Реализация
// visited — массив цветов вершин
int dfs(u: int, visited: bool[]):
int visitedVertices = 1
visited[u] = true // помечаем вершину как пройденную
for v: uv
E // проходим по смежным с u вершинам
if not visited[v] // проверяем, не находились ли мы ранее в выбранной вершине
visitedVertices += dfs(v, visited)
return visitedVertices
Проверка связности вершин в режиме онлайн
Задача: |
Дан пустой граф | , состоящий из вершин. Поступают запросы, каждый из которых — это пара вершин, между которыми надо добавить ребро. Необходимо в любой момент времени для двух выбранных вершин отвечать на вопрос, являются ли они связанными.
Алгоритм
Описываемая здесь идея довольна проста и будет основываться на системе непересекающихся множеств.
В каждом множестве будем хранить компоненты связности графа
. Тогда ответ на запросы второго типа будет заключаться в определении множеств, в которых находятся данные вершины, т.е. две вершины являются связанными, если они лежат в одной компоненте связности. Изначально все вершины находятся в разных компонентах связности. При добавлении ребра объединяем множества, в которых находятся его концы, если те различны.