11
правок
Изменения
Обернуть имя функции в тексте в mathrm
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Запустим обход в глубину от вершины <tex>s</tex>. При каждом посещении вершины <tex>v</tex> проверим, не является ли она искомой вершиной <tex>t</tex>. Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину для всех вершин, в которые есть ребро из <tex>v</tex>, причем он производится независимо от того, были эти вершины посещены ранее, или нет.
Функция <tex>\mathrm{countPaths(g, s, t)}</tex> принимает граф <tex>g</tex> в виде списка смежности, начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>.
'''countPaths'''(g, v, t)
=== Псевдокод ===
Пусть <tex>s</tex> — стартовая вершина, а <tex>t</tex> — конечная, для нее и посчитаем ответ. Будем поддерживать массив <tex>d</tex>, где <tex>d[v]</tex> — число путей из вершины <tex> s </tex> до вершины <tex>v</tex> и массив <tex>w</tex>, где <tex>w[v] = true</tex>, если ответ для вершины <tex>v</tex> уже посчитан, и <tex>w[v] = false</tex> в противном случае. Изначально <tex>w[i] = false</tex> для всех вершин <tex>i</tex>, кроме <tex>s</tex>, а <tex>d[s] = 1</tex>. Функция <tex>\mathrm{count(v)}</tex> будет возвращать ответ для вершины <tex>v</tex>. Удобнее всего это реализовать в виде рекурсивной функции с запоминанием. В этом случае значения массива <tex>d</tex> будут вычисляться по мере необходимости и не будут считаться лишний раз:
<tex> count(v) = \left \{
\begin{array}{ll}
d[v], & w[v]=''true '' \\
\sum\limits_{c}count(c), & w[v]=false
\end{array}
'''return''' answer
Значение функции <tex>\mathrm{count(v)}</tex> считается для каждой вершины один раз, а внутри нее рассматриваются все такие ребра <tex>\{e\ |\ end(e) = v\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма в худшем случае оценивается как <tex>O(V+E)</tex>, где <tex>V</tex> — число вершин графа, <tex>E</tex> — число ребер.
== Пример работы ==
| '''d''' || 1 || 0 || 0 || 0 || 0 || 0
|}
Сначала функция <tex>\mathrm{count}</tex> будет вызвана от вершины <tex>T</tex>. Ответ для нее еще не посчитан (<tex>w[T] = false</tex>), следовательно <tex>\mathrm{count}</tex> будет вызвана от вершин <tex>3</tex> и <tex>4</tex>. Для вершины <tex>3</tex> ответ также не посчитан (<tex>w[3] = false</tex>), следовательно <tex>\mathrm{count}</tex> будет вызвана уже для вершин <tex>2</tex> и <tex>S</tex>. А вот для них ответ мы уже можем узнать: для <tex>2</tex> он равен <tex>d[S]</tex>, так как это <tex>S</tex> — единственная вершина, ребро из которой входит в нее. Непосредственно для <tex>S</tex> ответ нам также известен. На текущий момент таблица будет выглядеть следующим образом:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|}
В самом начале для вычисления <tex>d[T]</tex> нам требовались значения <tex>d[3]</tex> и <tex>d[4]</tex>. Теперь нам известно значение <tex>d[3]</tex>, поэтому проследим за тем, как будет вычисляться <tex>d[4]</tex>. <tex>\mathrm{d[4] = count(3) + count(2) + count(1)}</tex>, но <tex>w[3] = true, w[2] = true</tex>, следовательно значения <tex>d[3]</tex> и <tex>d[2]</tex> мы уже знаем, и нам необходимо вызвать <tex>\mathrm{count(1)}</tex>. Ответ для этой вершины равен <tex>d[S]</tex>, так как это единственная вершина, ребро из которой входит в <tex>1</tex>. Обновим соответствующие значения массивов <tex>d</tex> и <tex>w</tex>:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
