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