Loại topo để tìm số đường dẫn đến t

Question

Tôi phải phát triển thuật toán O (| V | + | E |) liên quan đến kiểu topo, trong biểu đồ tuần hoàn hướng (DAG), xác định số lượng đường đi từ mỗi đỉnh của đồ thị là t (t là một nút có độ lệch 0). Tôi đã phát triển một biến thể của DFS như sau:

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 

Nhưng tôi không chắc chắn nếu thuật toán này có liên quan đến loại topo hoặc nếu tôi nên cơ cấu lại công việc của mình với một góc độ khác.

Answer 1

Nó có thể được thực hiện bằng động Lập trình và sắp xếp topo như sau:

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] 

Khi bạn làm xong, cho mỗi i trong [1,t], arr[i] cho biết số đường dẫn vi-vt

Bây giờ , chứng minh tuyên bố ở trên là dễ dàng (so sánh với thuật toán của bạn, mà tôi không biết nếu nó chính xác và cách chứng minh nó), nó được thực hiện bằng cách cảm ứng:

Cơ sở:arr[t] == 1 và thực sự có một đường đơn từ t đến t, dấu trống.
Giả thuyết: Lời khẳng định là đúng cho mỗi k trong phạm vi m < k <= t
Proof: Chúng tôi cần phải chứng minh tuyên bố là chính xác cho m.
Hãy xem từng cạnh ngoài từ vm: (v_m,v_i).
Do đó, số đường dẫn đến vt bắt đầu từ v_m sử dụng cạnh này (v_m,v_i). chính xác là arr[i] (giả thuyết cảm ứng). Tổng hợp tất cả các khả năng của các cạnh ngoài từ v_m, cung cấp cho chúng tôi tổng số đường dẫn từ v_m đến v_t - và đây chính xác là những gì thuật toán làm.
Như vậy, arr[m] = #paths from v_m to v_t

QED

Thời gian phức tạp:
Bước đầu tiên (topo loại) mất O(V+E).
Vòng lặp lặp lại tất cả các cạnh một lần và tất cả các đỉnh một lần, vì vậy nó cũng là O(V+E).
này cho chúng ta tổng phức tạp của O(V+E)