Một số cách tôi có thể đại diện cho biểu đồ có trọng số, hướng vào Java là gì?

Question

Tôi không thể sử dụng bất kỳ thư viện bên ngoài nào, vì vậy tôi đang cố gắng nghĩ ra một số cách để tự xây dựng cấu trúc dữ liệu. Tôi đã nghĩ có thể một cái gì đó như thế này:

public class Node{ 
    Set<Edge> adjacent; 
    int value; 
} 

public class Edge{ 
    Node target; 
    int weight; 
} 

Nhưng tôi đoán có lẽ có cách tốt hơn để làm điều đó.

Việc sử dụng cuối cùng của tôi cho biểu đồ này là chạy thuật toán Bellman Ford trên đó, nhưng rõ ràng là tôi cần một biểu đồ hoạt động trước!

Answer 1

Câu trả lời phụ thuộc rất nhiều vào các thuật toán bạn dự định áp dụng cho biểu đồ của mình.

Có hai cách phổ biến để biểu thị biểu đồ - một số adjacency list và adjacency matrix. Trong trường hợp của bạn, và ma trận kề là một mảng vuông của các số nguyên đại diện cho trọng số. Đại diện của bạn sử dụng danh sách kề.

Có các thuật toán hoạt động tốt hơn trên ma trận kề (ví dụ: thuật toán Floyd-Warshall). Các thuật toán khác hoạt động tốt hơn trên danh sách kề (ví dụ: thuật toán Dijkstra). Nếu đồ thị của bạn thưa thớt, sử dụng ma trận kề có thể bị cấm.

Answer 2

Như thường lệ, bạn có thể biểu thị biểu đồ dưới dạng Danh sách Adjacency hoặc Ma trận Adjacency. Sự lựa chọn thực sự phụ thuộc vào các chi tiết của vấn đề của bạn.

Sử dụng ma trận Adjacency, bạn có thể chỉ cần có ma trận số nguyên, biểu thị trọng số.

Nếu bạn quyết định có danh sách Adjacency, bạn có thể lưu trữ danh sách các số nguyên (giả sử các nút của biểu đồ của bạn được xác định bằng giá trị số nguyên), tương tự như những gì bạn đã thực hiện.

Answer 3

Bạn có thể sử dụng một nút như trong một đồ thị không trọng số, cầm một danh sách các nút mà nó được kết nối, và bổ sung thêm các trọng liên quan đến việc kết nối như:

public class Node{ 
    int value; 
    HashMap<Node,Integer> adjacency; 
}