Изменения
→Алгоритм проверки связности графа G
Дан [[Основные определения теории графов|неориентированный граф]] G. Необходимо проверить является ли он связным.
* '''Алгоритм'''
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу при входе в процедуру. Запустимся от какой-то вершины нашего графа. По окончании Если в конце работы процедуры dfs() сравним счётчик с нулём. Если они равныравен 0, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за O(M + N).
* '''Реализация'''
... //задание графа G с количеством вершин n и вершин S и T.
visited.assign(n, false); //в начале все вершины в графе ''не пройденные''
for(int i = 0; i < n; i++)
dfs(i);
