2
правки
Изменения
м
<code> answer = 0 '''countcountPaths'''(g, v, t)
answer += '''return''' 1
→Перебор всех возможных путей
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Запустим обход в глубину от вершины <tex>s</tex>. При каждом посещении вершины <tex>v</tex> проверим, не является ли она искомой вершиной <tex>t</tex>. Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину для всех вершин, в которые есть ребро из <tex>v</tex>, причем он производится независимо от того, были эти вершины посещены ранее, или нет.
Функция <tex>countPaths(g, s, t)</tex> принимает начальную вершину граф <tex>sg</tex> и конечную , начальную вершину <tex>ts</tex>. В глобальной переменной и конечную вершину <tex>answert</tex> содержится ответ.
'''if''' v == t
'''else'''
s = 0 '''for'''(всех <tex>to</tex> смежных с <tex>v</tex>) '''countin'''(to)g[v] s += '''countPathscount'''(sg, to, t) answer = 0 count(s) '''return''' answer </code>s
Время работы данного алгоритма в худшем случае <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе из <tex>s</tex> в <tex>t</tex>.
