Trong một directed graph (đồ thị có hướng, digraph), các cạnh có một hướng (A → B ≠ B → A). Trong một (đồ thị có trọng số), mỗi cạnh mang một (khoảng cách, thời gian, dung lượng). Kết hợp cả hai mô hình hóa các hệ thống thực tế nơi quan hệ là một chiều và có một chi phí.
Weighted directed graph:
A --5--> B
A --2--> C
C --1--> B
Adjacency list với trọng số:
A: [(B,5), (C,2)]
B: []
C: [(B,1)]
graph = {
'A': [('B', 5), ('C', 2)], # cạnh có hướng, có trọng số
'B': [],
'C': [('B', 1)],
}
# Đường đi ngắn nhất A->B là A->C->B = 2 + 1 = 3, không phải cạnh trực tiếp 5.
| Lĩnh vực | Đỉnh | Cạnh có hướng, có trọng số |
|---|---|---|
| Bản đồ / GPS | nút giao | đường một chiều + thời gian di chuyển |
| Mạng | router | liên kết + độ trễ/băng thông |
| Lập lịch tác vụ | tác vụ | phụ thuộc + thời lượng |
| Tài chính | tiền tệ | tỷ giá hối đoái |
| Mục tiêu | Thuật toán | Độ phức tạp |
|---|---|---|
| Đường đi ngắn nhất (trọng số không âm) | Dijkstra | O((V+E) log V) |
| Đường đi ngắn nhất (cạnh âm) | Bellman-Ford | O(VE) |
| Sắp thứ tự với phụ thuộc | Topological sort | O(V+E) |
| Phát hiện chu trình / khả năng tới được | DFS | O(V+E) |
Hướng và trọng số là cái biến một graph trừu tượng thành một mô hình trung thực của các bài toán định tuyến, lập lịch, và phụ thuộc điều khiển các ứng dụng thực tế.
Lựa chọn thuật toán xoay quanh các thuộc tính này — ví dụ, trọng số âm loại trừ Dijkstra và đòi hỏi Bellman-Ford.
Thư viện câu hỏi phỏng vấn IT với đáp án chi tiết — từ Junior đến Senior.
Ủng hộ