68
правок
Изменения
Нет описания правки
== Алгоритм проверки связности ВСЕГО графа G ==
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу перед выходом из процедуры. Запустимся от какой-то вершины нашего графа. По окончании работы процедуры dfs() сравним счётчик с нулём. Если они равны, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за O(M + N).
=== Реализация ===
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах
int k = 0;
void dfs(int u)
{
k--;
visited[u] = true; //помечаем вершину как пройденную
for (v таких, что (u, v) - ребро в G) //проходим по смежным с u вершинам
if (!visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
dfs(v);
}
int main()
{
... //задание графа G с количеством вершин n и вершин S и T.
visited.assign(n, false); //в начале все вершины в графе ''не пройденные''
int k = n;
for(int i = 0; i < n; i++)
dfs(i);
if(k == 0)
//вывести, что граф связен
else
//вывести, что граф несвязен
return 0;
}
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
