Những cách khác nhau để thực hiện DAG trong java

Question

Tôi đang thực hiện DAG và tự hỏi liệu sau đây là cách duy nhất để đại diện cho nó trong Java:

class Node{ 
List<Node> parents; 
List<Node> successors; 
int value; } 

class DAG{ 
Node root; // assuming only one root exists 
} 

Tôi đang tìm kiếm một cái gì đó đơn giản hơn không hai danh sách dành cho cha mẹ và trẻ em.
là nó có thể? Ngoài ra tôi có một vấn đề với đại diện này rằng nếu tôi đạt đến một nút cụ thể x và muốn đường dẫn từ x đến nút gốc, làm thế nào tôi có thể tìm thấy nó mà không cần phải thông qua tất cả các bậc cha mẹ?

Answer 1

Để đơn giản hóa cấu trúc biểu đồ được chỉ dẫn của bạn, không cần thiết cho các nút có liên kết quay lại tổ tiên của chúng. Tôi cũng sẽ đặt lớp Node bên trong lớp DAG của bạn. Về mặt khái niệm, biểu diễn này càng có ý nghĩa hơn vì trong một đồ thị có hướng, nếu nút A liên kết đến nút B, không cần phải có đường từ B đến A. Trên thực tế không thể có đường dẫn theo cả hai hướng vì đó sẽ là một chu kỳ.

public class DAG { 
    Node root; // assuming only one root exists 

    public static class Node{ 
     List<Node> successors; 
     int value; 
    } 
} 

Để tìm đường dẫn từ gốc đến nút cụ thể, bạn cần chạy thuật toán để tìm kiếm qua biểu đồ. Điều đó có nghĩa là có thể truy cập các nút khác trong biểu đồ, có thể đệ quy, cho đến khi bạn xác định vị trí nút đã cho. Nếu bạn muốn tránh lặp lại những loại tính toán, bạn cũng có thể lưu trữ các đường đi từ gốc để một nút cho trước với một cái gì đó như thế này:

class PathMap { 
    HashMap<DAG.Node, List<DAG.Node> > pathMap; 

    public List<DAG.Node> getPathFromRoot(DAG.Node n) { 
    List<DAG.Node> pathFromRoot = pathMap.get(n); 
    return pathFromRoot; 
    } 
} 

Bây giờ có thể có những con đường khác nhau từ gốc đến một nút đã cho. Trong trường hợp đó, bạn có thể muốn triển khai shortest-path-first algorithm để tìm và lưu trữ đường dẫn tối ưu. Xem số dzone article cho mã giả này.

Answer 2

Việc thả danh sách phụ huynh có hợp lý hay không tùy thuộc vào trường hợp sử dụng thông thường của bạn. Như Thorn đã chỉ ra, về nguyên tắc, bạn có thể bỏ cha mẹ trong một DAG như chúng được đưa ra bởi các trẻ em (hoặc cha mẹ). Tuy nhiên, nếu trong các ứng dụng của bạn, bạn thường cần tìm một số tổ tiên của một nút cụ thể, danh sách cha mẹ có thể giúp thực hiện thuật toán nhanh để thực hiện điều đó (vì bạn không phải luôn luôn bắt đầu từ gốc và có khả năng đi qua toàn bộ đồ thị, thay vì đi ngược lại khi cần thiết từ nút đã cho).

Tôi đã thêm điều này làm nhận xét cho câu trả lời của Thorn, nhưng không có đủ đại diện để nhận xét. Vì vậy, cảm thấy tự do để bao gồm nó trong câu trả lời của mình.