Изменения
Нет описания правки
== Задача Алгоритм проверки наличия пути из S в T ==1) * '''Задача'''Дан граф G и две вершины S и T. Необходимо проверить существует ли путь из вершины S в вершину T по рёбрам графа G.
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины S и проверять при каждом посещении вершины, не является ли она искомой вершиной T.
Так как в первый момент времени все пути в графе "белые", то если вершина T и была достижима из S, то по [[Лемма о белых путях|Лемме о белых путях]] в какой-то момент времени мы зайдём в вершину T, чтобы её покрасить. Время работы алгоритма O(M + N).
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах
return 0;
}
== Алгоритм проверки связности ВСЕГО графа G ==
* '''Задача'''
Дан [[Основные определения теории графов|неориентированный граф]] G. Необходимо проверить является ли он связным.
* '''Алгоритм'''
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу перед выходом из процедуры. Запустимся от какой-то вершины нашего графа. По окончании работы процедуры dfs() сравним счётчик с нулём. Если они равны, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за O(M + N).
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах
int k = 0;
