số đường dẫn trong biểu đồ

Question

số lượng đường dẫn trong biểu đồ được chỉ định có thể được tính như thế nào? Có bất kỳ thuật toán nào cho mục đích này không?

Chúc

EDIT: Đồ thị không phải là một cái cây.

Answer 1

Tôi không tin có gì nhanh hơn việc duyệt qua biểu đồ, bắt đầu từ gốc.

Trong pseudo-code -

visit(node) { 
    node.visited = true; 
    for(int i = 0; i < node.paths.length; ++i) { 
    ++pathCount; 
    if (!node.paths[i].visited) 
     visit(node.paths[i]); 
    } 

} 

Answer 2

Tất cả các truy cập tìm kiếm Tôi thấy là dành cho số lượng đường đi từ một nút cho một nút cho trước. Nhưng đây là một thuật toán nên tìm tổng số đường dẫn ở bất kỳ đâu trong biểu đồ, cho bất kỳ bản đồ tuần hoàn nào. (Nếu có chu kỳ, có một số lượng vô hạn của con đường trừ khi bạn xác định rằng con đường lặp đi lặp lại nhất định được loại trừ.)

Label mỗi nút với số lượng đường dẫn mà kết thúc tại nút đó:

While not all nodes are labeled: 
    Choose an unlabeled node with no unlabeled ancestors. 
    (An implementation might here choose any node, and recursively 
    process any unlabeled ancestors of that node first.) 
    Label the node with one plus the sum of the labels on all ancestors. 
    (If a node has no ancestors, its label is simply 1.) 

Bây giờ, chỉ cần thêm nhãn trên tất cả các nút.

Nếu bạn không muốn tính các đường dẫn "độ dài bằng không", hãy trừ số lượng nút.

Answer 3

Nếu nó thực sự là một cây, số lượng đường dẫn bằng số nút-1 nếu bạn đếm đường dẫn đến nút nội bộ. Nếu bạn chỉ đếm đường dẫn đến lá, số đường dẫn bằng với số lượng lá. Vì vậy, thực tế là chúng ta đang nói về cây đơn giản hóa các vấn đề để chỉ đếm các nút hoặc lá. Một thuật toán BFS hoặc DFS đơn giản sẽ là đủ.

Answer 4

Nếu biểu đồ không phải là một cây, sẽ có đường dẫn vô hạn - đi bộ vòng lặp bất kỳ lúc nào.

Answer 5

Bạn có thể sử dụng depth-first search. Tuy nhiên, bạn không chấm dứt tìm kiếm khi bạn tìm thấy một đường dẫn từ đầu đến đích, cách tìm kiếm theo chiều sâu đầu tiên bình thường. Thay vào đó, bạn chỉ cần thêm vào số lượng đường dẫn và quay trở lại từ nút đó như thể nó là một kết thúc chết. Đây có lẽ không phải là phương pháp nhanh nhất, nhưng nó sẽ hoạt động.

Bạn cũng có thể sử dụng tìm kiếm theo chiều rộng, nhưng sau đó bạn cần tìm cách chuyển thông tin về số lượng đường dẫn tiến lên (hoặc lùi) qua cây khi bạn tìm kiếm. Nếu bạn có thể làm điều đó, nó có lẽ sẽ nhanh hơn nhiều.

Answer 6

Giả sử đồ thị là tuần hoàn (một DAG), bạn có thể tạo phân loại topo của các đỉnh và hơn là lập trình động để tính toán số lượng đường dẫn riêng biệt. Nếu bạn muốn in tất cả các đường dẫn, không có nhiều sử dụng trong việc thảo luận về ký hiệu O lớn vì số lượng đường dẫn có thể được theo cấp số nhân trên số đỉnh.

Pseudo-code:

paths := 0 
dp[i] := 0, for all 0 <= i < n 
compute topological sorting and store on ts 
for i from n - 1 to 0 
    for all edges (ts[i], v) // outbound edges from ts[i] 
     dp[ts[i]] := 1 + dp[ts[i]] + dp[v] 
    paths := paths + dp[ts[i]] 

print paths 

Edit: Bug trên mã

Answer 7

Hãy A là ma trận kề của một đồ thị G. Sau đó, A^n (tức làA nhân n lần với chính nó) có tính chất thú vị sau:

Mục ở vị trí (i,j) của A^n bằng với số con đường khác nhau có độ dài n từ đỉnh i đến đỉnh j.

Do đó:

• đại diện cho đồ thị như một ma trận kề A
• nhân A nó với chính nó lặp đi lặp lại cho đến khi bạn cảm thấy buồn chán
• trong mỗi bước: tính tổng của tất cả các yếu tố ma trận và thêm nó đến kết quả, bắt đầu từ 0

Có thể là khôn ngoan để kiểm tra xem liệu G có chứa chu kỳ hay không, vì trong trường hợp này nó chứa vô hạn m bất kỳ đường dẫn nào. Để phát hiện các chu kỳ, đặt tất cả các trọng số cạnh thành -1 và sử dụng Bellman-Ford.

Answer 8

admat cho độ dài 1 đường đi giữa các đỉnh;

admat^2 cho chiều dài 2 đường đi giữa các đỉnh;

admat^3 cho chiều dài 3 đường đi giữa các đỉnh;

Tìm mẫu chưa?