Использование обхода в глубину для проверки связности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (Добавлен раздел См. также)
Строка 1: Строка 1:
== Алгоритм проверки наличия пути из s в t ==
+
== Алгоритм проверки наличия пути из одной вершины в другую ==
  
 
=== Задача ===
 
=== Задача ===
Строка 45: Строка 45:
 
         '''if''' ('''not''' visited[v])              //проверяем, не находились ли мы ранее в выбранной вершине
 
         '''if''' ('''not''' visited[v])              //проверяем, не находились ли мы ранее в выбранной вершине
 
             dfs(v);
 
             dfs(v);
 +
 +
== См. также ==
 +
*[[Обход в глубину, цвета вершин]]
 +
*[[Лемма о белых путях]]
 +
*[[Использование обхода в глубину для поиска цикла в ориентированном графе]]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обход в глубину]]
 
[[Категория: Обход в глубину]]

Версия 05:30, 9 декабря 2014

Алгоритм проверки наличия пути из одной вершины в другую

Задача

Дан граф [math]G[/math] и две вершины [math]s[/math] и [math]t[/math]. Необходимо проверить, существует ли путь из вершины [math]s[/math] в вершину [math]t[/math] по рёбрам графа [math]G[/math].

Алгоритм

Небольшая модификация алгоритма обхода в глубину. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины [math]s[/math] и проверять при каждом посещении вершины, не является ли она искомой вершиной [math]t[/math]. Так как в первый момент времени все пути в графе "белые", то если вершина [math]t[/math] и была достижима из [math]s[/math], то по лемме о белых путях в какой-то момент времени мы зайдём в вершину [math]t[/math], чтобы её покрасить. Время работы алгоритма [math]O(M + N)[/math].

Реализация

bool[] visited;                                 //массив цветов вершин

bool dfs(u: int)              
    if (u == t)
        return true;    
    visited[u] = true;                            //помечаем вершину как пройденную
    for (v таких, что (u, v) — ребро в G)       //проходим по смежным с u вершинам
        if (not visited[v])               //проверяем, не находились ли мы ранее в выбранной вершине
            if (dfs(v))
                return true;
    return false;

Алгоритм проверки связности графа G

Задача

Дан неориентированный граф [math]G[/math]. Необходимо проверить, является ли он связным.

Алгоритм

Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу при входе в процедуру. Запустим алгоритм от некоторой вершины нашего графа. Если в конце работы процедуры dfs() счётчик равен нулю, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за [math]O(M + N)[/math].

Реализация

bool[] visited;                                 //массив цветов вершин
int k = n;                                      //счетчик изначально равен количеству вершин

function dfs(u: int)              
    k--;
    visited[u] = true;                            //помечаем вершину как пройденную
    for (v таких, что (u, v) — ребро в G)       //проходим по смежным с u вершинам
        if (not visited[v])               //проверяем, не находились ли мы ранее в выбранной вершине
            dfs(v);

См. также