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:Loại topo để tìm số đường dẫn đến t
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.
tôi giả sử đồ thị của bạn là một DAG (nếu không có điểm trên nói về loại topo, cũng không phải về số con đường, có thể có vô số những) – amit
@amit Vâng, Tôi đặt trong câu hỏi "đồ thị tuần hoàn hướng". Tôi đã chỉnh sửa để thêm từ viết tắt "DAG" – Stratford
Bản ngã của bạn là chính xác, bạn sẽ tìm thấy số cách để t. Và bạn làm điều đó theo phương thức topo: ngay khi u đỉnh có màu đen, giá trị path_to_t (u) là chính xác - nó tương ứng với việc đẩy đỉnh trong ngăn xếp trong bản ngã loại topo. –