47
правок
Изменения
Изменена структура статьи, псевдокод отформатирован и раскрашен.
== Алгоритм проверки наличия пути из s в t ==
Дан граф <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо проверить, существует ли путь из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины <tex>s</tex> и проверять при каждом посещении вершины, не является ли она искомой вершиной <tex>t</tex>.
Так как в первый момент времени все пути в графе "белые", то если вершина <tex>t</tex> и была достижима из <tex>s</tex>, то по [[Лемма о белых путях|лемме о белых путях]] в какой-то момент времени мы зайдём в вершину <tex>t</tex>, чтобы её покрасить. Время работы алгоритма <tex>O(M + N)</tex>.
bool dfs(int u)
{
'''if''' (u == t) '''return ''' true; visited[u] = true; //помечаем вершину как пройденную '''for ''' (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам '''if ''' (!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 существует";
std::out << "Пути из S в T нет";
'''return ''' 0;
}
== Алгоритм проверки связности графа G ==
Дан [[Основные определения теории графов|неориентированный граф]] <tex>G</tex>. Необходимо проверить, является ли он связным.
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу при входе в процедуру. Запустимся от какой-то вершины нашего графа. Если в конце работы процедуры dfs() счётчик равен нулю, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за <tex>O(M + N)</tex>.
int k = 0;
{
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); //в начале все вершины в графе ''не пройденные''
k = n;
'''for''' (int i = 0; i < n; i++)
dfs(i);
'''if''' (k == 0) std::out << "Граф связен"; //вывести, что граф связен '''else''' std::out << "Граф несвязен"; //вывести, что граф несвязен '''return ''' 0;
}
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
