Изменения

Дан [[Основные определения теории графов|неориентированный граф]]. Необходимо проверить является ли он связным.

Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы считать сколько вершин мы посетили во время обхода.

Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу перед выходом из процедуры. Запустимся от какой-то вершины нашего графа(если он связен, то мы посетим все остальные). По окончании работы процедуры dfs() сравним счётчик с нулём. Если они равны, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то в графе несколько компонент связности. Работает алгоритм за O(M + N).