Các vấn đề với thuật toán phụ thuộc đơn giản

Question

Trong ứng dụng web của tôi, chúng tôi có nhiều trường tổng hợp các trường khác và các trường đó tổng hợp nhiều trường hơn. Tôi biết rằng đây là đồ thị theo chu kỳ.

Khi tải trang, tôi tính giá trị cho tất cả các trường. Những gì tôi thực sự cố gắng làm là chuyển đổi DAG của tôi thành một danh sách một chiều có chứa thứ tự hiệu quả để tính toán các trường.

Ví dụ: A = B + D, D = B + C , B = C + E Thứ tự tính hiệu quả: E -> C -> B -> D -> A

Ngay bây giờ thuật toán của tôi chỉ đơn giản chèn vào danh sách lặp đi lặp lại, nhưng tôi đã gặp phải một số tình huống bắt đầu phá vỡ. Tôi đang nghĩ cái gì sẽ là cần thiết thay vào đó sẽ là tìm ra tất cả các phụ thuộc vào một cấu trúc cây, và từ đó biến đổi nó thành dạng một chiều? Có một thuật toán đơn giản để chuyển đổi một cây thành một thứ tự hiệu quả?

Answer 1

Bạn đang tìm kiếm topological sort? Điều này áp đặt một thứ tự (một chuỗi hoặc danh sách) trên một DAG. Nó được sử dụng bởi, ví dụ, bảng tính, để tìm ra sự phụ thuộc giữa các ô để tính toán.

Answer 2

Điều bạn muốn là tìm kiếm theo chiều sâu.

function ExamineField(Field F) 
{ 
    if (F.already_in_list) 
     return 

    foreach C child of F 
    { 
     call ExamineField(C) 
    } 

    AddToList(F) 
} 

Sau đó, chỉ cần gọi ExamineField() trên mỗi trường lần lượt và danh sách sẽ được điền theo thứ tự tối ưu theo thông số của bạn.

Lưu ý rằng nếu các trường là cyclic (nghĩa là, bạn có thứ gì đó như A = B + C, B = A + D) thì thuật toán phải được sửa đổi để nó không đi vào vòng lặp vô tận .

Ví dụ của bạn, các cuộc gọi sẽ đi:

ExamineField(A) 
    ExamineField(B) 
    ExamineField(C) 
     AddToList(C) 
    ExamineField(E) 
     AddToList(E) 
    AddToList(B) 
    ExamineField(D) 
    ExamineField(B) 
     (already in list, nothing happens) 
    ExamineField(C) 
     (already in list, nothing happens) 
    AddToList(D) 
    AddToList(A) 
ExamineField(B) 
    (already in list, nothing happens) 
ExamineField(C) 
    (already in list, nothing happens) 
ExamineField(D) 
    (already in list, nothing happens) 
ExamineField(E) 
    (already in list, nothing happens) 

Và danh sách sẽ kết thúc C, E, B, D, A.