hoạt động Matrix để liệt kê tất cả những con đường thông qua n-partite graph

Question

Tôi có một n-partite (vô hướng) đồ thị, được đưa ra như một ma trận kề, ví dụ này ở đây:

 
    a b c d 
a 0 1 1 0 
b 0 0 0 1 
c 0 0 0 1 
d 0 0 0 0 

Tôi muốn biết nếu có một tập hợp các phép toán ma trận mà tôi có thể áp dụng cho ma trận này, điều này sẽ dẫn đến ma trận "liệt kê" tất cả các đường dẫn (có độ dài n, tức là thông qua tất cả các phân vùng) trong biểu đồ này. Đối với ví dụ trên, có các đường dẫn a-> b-> d và a-> c-> d. Do đó, tôi muốn nhận ma trận sau đây:

 
a b c d 
1 1 0 1 
1 0 1 1 

Đường dẫn đầu tiên chứa các nút a, b, d và nút thứ hai a, c, d. Nếu cần, ma trận kết quả có thể có một số dòng tất cả 0, như sau:

 
a b c d 
1 1 0 1 
0 0 0 0 
1 0 1 1 
0 0 0 0 

Cảm ơn!

P.S. Tôi đã xem xét các thuật toán để tính toán sự đóng cửa chuyển tiếp, nhưng chúng thường chỉ cho biết nếu có một đường dẫn giữa hai nút, và không trực tiếp các nút nào nằm trên đường dẫn đó.

Answer 1

Một điều bạn có thể làm là tính toán sức mạnh thứ n của ma trận A. Kết quả sẽ cho bạn biết có bao nhiêu đường dẫn có chiều dài n từ bất kỳ đỉnh nào đến bất kỳ đỉnh nào khác.

Bây giờ nếu bạn quan tâm đến việc biết tất cả các đỉnh dọc theo con đường, tôi không nghĩ rằng việc sử dụng các hoạt động thuần túy là cách để đi. Lưu ý rằng bạn có biểu đồ n-partite, tôi sẽ thiết lập cấu trúc dữ liệu như sau: (Ghi nhớ rằng chi phí không gian sẽ đắt đối với tất cả trừ các giá trị nhỏ.)

Mỗi cột sẽ có một mục nhập mỗi nút trong biểu đồ của chúng tôi. Cột thứ n sẽ chứa 1 trong trường hợp nút này có thể truy cập được trên lần lặp thứ n từ đỉnh bắt đầu được chỉ định của chúng tôi hoặc bắt đầu thiết lập, và không nếu không. Mỗi mục nhập cột cũng sẽ chứa một danh sách các con trỏ ngược tới các đỉnh trong cột n-1 dẫn đến đỉnh này trong cột thứ n. (Điều này giống như thuật toán viterbi, ngoại trừ việc chúng ta phải duy trì một danh sách các backpointers cho mỗi mục thay vì chỉ một.) Sự phức tạp của việc này là (m^2) * n, trong đó m là số đỉnh trong biểu đồ và n là độ dài của đường dẫn mong muốn.

Tôi hơi bối rối bởi ma trận hàng đầu của bạn: với biểu đồ không được xác định, tôi cho rằng ma trận kề sẽ đối xứng.

Answer 2

Không, Không có ma trận thuần túy nào để tạo tất cả đường dẫn. Vui lòng sử dụng thuật toán tổ hợp thuần túy.

'Một điều bạn có thể làm là tính toán sức mạnh thứ n của ma trận A. Kết quả sẽ cho bạn biết có bao nhiêu đường dẫn có độ dài n từ bất kỳ đỉnh nào đến bất kỳ đỉnh nào khác'.

Sức mạnh của matriax tạo ra lối đi không phải đường dẫn.