47
правок
Изменения
м
Нет описания правки
== Алгоритм проверки наличия пути из одной вершины в другую между двумя вершинами ==
=== Задача ===
'''if''' (u == t)
'''return''' ''true'';
visited[u] = ''true''; //помечаем вершину как пройденную
'''for''' (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам
'''if''' ('''not''' visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
'''if''' (dfs(v))
'''return''' ''true'';
=== Реализация ===
'''bool[]''' visited; //массив цветов вершин '''int''' k = n; //счетчик изначально равен количеству вершин
function dfs(u: '''int''')
k--;
visited[u] = ''true''; //помечаем вершину как пройденную '''for''' (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам '''if''' ('''not''' visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
dfs(v);
