68
правок
Изменения
Нет описания правки
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу перед выходом из процедуры. Запустимся от какой-то вершины нашего графа. По окончании работы процедуры dfs() сравним счётчик с нулём. Если они равны, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то в графе несколько компонент связности. Работает алгоритм за O(M + N).
== Псевдокод = Реализация === string color[]vector<bool> visited; //изначально массив color заполнен значениями white.вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах bool dfs(int count u) { if(u == t) return true; visited[u] = ntrue; //счётчик количества вершин; изначально равен количеству вершин в графепомечаем вершину как пройденную bool if_connected for (v таких, что (u, v) - ребро в G) //проходим по смежным с u вершинам dfs if (0!visited[v]); //запуск от какой-то вершиныпроверяем, не находились ли мы ранее в выбранной вершине if(count == 0dfs(v)) return retrun true; else
return false;
}
int dfsmain(int u) { ... //процедура обхода в глубинузадание графа G с количеством вершин n и вершин S и T. запуск от номера вершины forvisited.assign(v: uv - реброn, false); //в начале все вершины в графе ''не пройденные'' if(color[v] == white) dfs(vs)) std::out << "Путь из S в T существует"; color[u] = black else std::out << "Пути из S в T нет"; count-- return 0; }
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
