Использование обхода в глубину для проверки связности
Версия от 07:45, 10 ноября 2010; Kasetkin (обсуждение | вклад)
Содержание
Задача
Дан неориентированный граф. Необходимо проверить является ли он связным.
Идея
Небольшая модификация алгоритма обхода в глубину. Смысл алгоритма заключается в том, чтобы считать сколько вершин мы посетили во время обхода.
Алгоритм
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу перед выходом из процедуры. Запустимся от какой-то вершины нашего графа(если он связен, то мы посетим все остальные). По окончании работы процедуры dfs() сравним счётчик с нулём. Если они равны, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то в графе несколько компонент связности.
Псевдокод
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--;