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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
Небольшая модификация алгоритма обхода в глубину позволяет проверить связность неориентированного графа.
+
== Задача ==
Идея алгоритма заключается в том, чтобы считать сколько вершин мы посетили во время обхода.
+
Дан неориентированный граф. Необходимо проверить является ли он связным.
  
 +
== Алгоритм ==
 +
Небольшая модификация алгоритма обхода в глубину. Идея алгоритма заключается в том, чтобы считать сколько вершин мы посетили во время обхода.
  
 +
== Псевдокод ==
 
  string color[];        //изначально массив color заполнен значениями white.
 
  string color[];        //изначально массив color заполнен значениями white.
 
  int count = n;          //счётчик количества вершин; изначально равен количеству вершин в графе
 
  int count = n;          //счётчик количества вершин; изначально равен количеству вершин в графе

Версия 07:36, 10 ноября 2010

Задача

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

Алгоритм

Небольшая модификация алгоритма обхода в глубину. Идея алгоритма заключается в том, чтобы считать сколько вершин мы посетили во время обхода.

Псевдокод

string color[];         //изначально массив color заполнен значениями white.
int count = n;          //счётчик количества вершин; изначально равен количеству вершин в графе
bool if_connected()    
  dfs(0);               //запуск от  какой-то вершины
  if(count == 0)
    return true;
  else
    return false;

int dfs(int u)         //процедура обхода в глубину. запуск от номера вершины
    for(v: uv - ребро)
    if(color[v] == white)
      dfs(v);
  color[u] = black;
  count--;