Изменения

Перейти к: навигация, поиск

Использование обхода в глубину для проверки связности

1232 байта убрано, 05:18, 9 декабря 2014
Код на плюсах превращен в псевдокод
=== Реализация ===
vector<bool> visited; //вектор для хранения информации о ''пройденных'bool[]' и ''не пройденных'' вершинахvisited; //массив цветов вершин '''bool''' dfs(u: '''int''' u) {
'''if''' (u == t)
'''return''' ''true'';
visited[u] = ''true''; //помечаем вершину как пройденную
'''for''' (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам '''if''' ('''not''' visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
'''if''' (dfs(v))
'''return''' ''true'';
'''return''' ''false'';
}
'''int''' main()
{
... //задание графа G с количеством вершин n и вершин S и T.
visited.assign(n, ''false''); //в начале все вершины в графе ''не пройденные''
'''if''' (dfs(s))
std::out << "Путь из S в T существует";
'''else'''
std::out << "Пути из S в T нет";
'''return''' 0;
}
== Алгоритм проверки связности графа G ==
=== Алгоритм ===
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу при входе в процедуру. Запустимся Запустим алгоритм от какой-то вершины нашего графа. Если в конце работы процедуры dfs() счётчик равен нулю, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за <tex>O(M + N)</tex>.
=== Реализация ===
vector<'''bool[]'''> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинахмассив цветов вершин '''int''' k = 0n; //счетчик изначально равен количеству вершин
void function dfs(u: '''int''' u) {
k--;
visited[u] = ''true''; //помечаем вершину как пройденную
'''for''' (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам '''if''' ('''not''' visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
dfs(v);
}
'''int''' main()
{
... //задание графа G с количеством вершин n и вершин S и T.
visited.assign(n, ''false''); //в начале все вершины в графе ''не пройденные''
k = n;
'''for''' ('''int''' i = 0 '''to''' n - 1)
dfs(i);
'''if''' (k == 0)
std::out << "Граф связен"; //вывести, что граф связен
'''else'''
std::out << "Граф несвязен"; //вывести, что граф несвязен
'''return''' 0;
}
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
Kamensky
47
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/41989»

Навигация