Топологическая сортировка, чтобы найти количество путей к t

Question

Мне нужно разработать алгоритм O (| V | + | E |), связанный с топологическим типом, который в направленном ациклическом графе (DAG) определяет количество путей из каждая вершина графа к t (t - узел с внешней степенью 0). Я разработал модификацию ДФСА следующим образом:

DFS(G,t): 
    for each vertex u ∈ V do 
     color(u) = WHITE 
     paths_to_t(u) = 0 
    for each vertex u ∈ V do 
     if color(u) == WHITE then 
      DFS-Visit(u,t) 

DFS-Visit(u,t): 
    color(u) = GREY 
    for each v ∈ neighbors(u) do 
     if v == t then 
      paths_to_t(u) = paths_to_t(u) + 1 
     else then 
      if color(v) == WHITE then 
       DFS-Visit(v) 
      paths_to_t(u) = paths_to_t(u) + paths_to_t(v) 
    color(u) = BLACK 

Но я не уверен, что этот алгоритм связан с топологической сортировкой, или если я должен перестроить свою работу с другой точкой зрения.

Answer 1

Это может быть сделано с помощью динамического программирования и топологическую сортировку следующим образом:

Topological sort the vertices, let the ordered vertices be v1,v2,...,vn 
create new array of size t, let it be arr 
init: arr[t] = 1 
for i from t-1 to 1 (descending, inclusive): 
    arr[i] = 0 
    for each edge (v_i,v_j) such that i < j <= t: 
     arr[i] += arr[j] 

Когда вы закончите, для каждого i в [1,t], arr[i] указывает количество путей от vi к vt

сейчас , доказательство вышеуказанного утверждения легко (по сравнению с вашим алгоритмом, о котором я не знаю, правильно ли это и как его доказать), это делается по индукции:

База:arr[t] == 1, и действительно есть один путь от t до t, пустой.
Гипотеза: утверждение верно для каждого k в диапазоне m < k <= t
Доказательство: Нам нужно показать утверждение верно для m.
Давайте посмотрим на каждый внешний край от vm: (v_m,v_i).
Таким образом, количество путей до vt, начиная с v_m, которые используют этот край (v_m,v_i). составляет точно arr[i] (индукционная гипотеза). Суммируя все возможности внешних краев от v_m, мы получаем общее количество путей от v_m до v_t - и это именно то, что делает алгоритм.
Таким образом, arr[m] = #paths from v_m to v_t

КЭД

Временная сложность:
Первый шаг (топологическая сортировка) принимает O(V+E).
Цикл повторяет все края один раз, а все вершины один раз, так что это также O(V+E).
Это дает нам общую сложность O(V+E)