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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Код раскрашен)
(Код на плюсах превращен в псевдокод)
Строка 12: Строка 12:
 
=== Реализация ===
 
=== Реализация ===
  
−
  vector<bool> visited;                            //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах
+
  '''bool[]''' visited;                                //массив цветов вершин
−
+
 
−
  '''bool''' dfs('''int''' u)               
+
  '''bool''' dfs(u: '''int''')               
−
{
 
 
     '''if''' (u == t)
 
     '''if''' (u == t)
 
         '''return''' ''true'';     
 
         '''return''' ''true'';     
 
     visited[u] = ''true'';                            //помечаем вершину как пройденную
 
     visited[u] = ''true'';                            //помечаем вершину как пройденную
−
     '''for''' (v таких, что (u, v) — ребро в G)   //проходим по смежным с u вершинам
+
     '''for''' (v таких, что (u, v) — ребро в G)       //проходим по смежным с u вершинам
−
         '''if''' ('''not''' visited[v])                   //проверяем, не находились ли мы ранее в выбранной вершине
+
         '''if''' ('''not''' visited[v])               //проверяем, не находились ли мы ранее в выбранной вершине
 
             '''if''' (dfs(v))
 
             '''if''' (dfs(v))
 
                 '''return''' ''true'';
 
                 '''return''' ''true'';
 
     '''return''' ''false'';
 
     '''return''' ''false'';
−
}
 
−
 
−
'''int''' main()
 
−
{
 
−
    ...                                          //задание графа G с количеством вершин n и вершин S и T.
 
−
    visited.assign(n, ''false'');                    //в начале все вершины в графе ''не пройденные''
 
−
    '''if''' (dfs(s))
 
−
          std::out << "Путь из S в T существует";
 
−
    '''else'''
 
−
          std::out << "Пути из S в T нет";
 
−
    '''return''' 0;
 
−
}
 
  
 
== Алгоритм проверки связности графа G ==
 
== Алгоритм проверки связности графа G ==
Строка 45: Строка 32:
 
=== Алгоритм ===
 
=== Алгоритм ===
  
−
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу при входе в процедуру. Запустимся от какой-то вершины нашего графа. Если в конце работы процедуры dfs() счётчик равен нулю, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за <tex>O(M + N)</tex>.
+
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу при входе в процедуру. Запустим алгоритм от какой-то вершины нашего графа. Если в конце работы процедуры dfs() счётчик равен нулю, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за <tex>O(M + N)</tex>.
  
 
=== Реализация ===
 
=== Реализация ===
  
−
  vector<'''bool'''> visited;                             //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах
+
  '''bool[]''' visited;                                 //массив цветов вершин
−
  '''int''' k = 0;
+
  '''int''' k = n;                                     //счетчик изначально равен количеству вершин
 
   
 
   
−
  void dfs('''int''' u)               
+
  function dfs(u: '''int''')               
−
{
 
 
     k--;
 
     k--;
 
     visited[u] = ''true'';                            //помечаем вершину как пройденную
 
     visited[u] = ''true'';                            //помечаем вершину как пройденную
−
     '''for''' (v таких, что (u, v) — ребро в G)   //проходим по смежным с u вершинам
+
     '''for''' (v таких, что (u, v) — ребро в G)       //проходим по смежным с u вершинам
−
         '''if''' ('''not''' visited[v])                   //проверяем, не находились ли мы ранее в выбранной вершине
+
         '''if''' ('''not''' visited[v])               //проверяем, не находились ли мы ранее в выбранной вершине
 
             dfs(v);
 
             dfs(v);
−
}
 
−
 
−
'''int''' main()
 
−
{
 
−
    ...                                          //задание графа G с количеством вершин n и вершин S и T.
 
−
    visited.assign(n, ''false'');                    //в начале все вершины в графе ''не пройденные''
 
−
    k = n;
 
−
    '''for''' ('''int''' i = 0 '''to''' n - 1)
 
−
        dfs(i);
 
−
    '''if''' (k == 0)
 
−
        std::out << "Граф связен";                //вывести, что граф связен
 
−
    '''else''' 
 
−
        std::out << "Граф несвязен";              //вывести, что граф несвязен
 
−
    '''return''' 0;
 
−
}
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обход в глубину]]
 
[[Категория: Обход в глубину]]

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

Алгоритм проверки наличия пути из s в t

Задача

Дан граф [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);
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Использование_обхода_в_глубину_для_проверки_связности&oldid=41989»