Đồ thị có hướng dưới dạng danh sách kề là gì?

🧠 1. Đồ thị có hướng là gì?

Đồ thị có hướng (Directed Graph) là một tập các đỉnh (node) và các cạnh (edge), trong đó mỗi cạnh có chiều, tức là chỉ đi được từ đỉnh A đến đỉnh B, không đi ngược lại.

Ví dụ: Nếu có một cạnh từ A đến B thì bạn chỉ đi được A → B, không đi được B → A (trừ khi có cạnh ngược lại).

📦 2. Danh sách kề (Adjacency List) là gì?

Danh sách kề là một cách phổ biến để biểu diễn đồ thị trong lập trình. Thay vì sử dụng ma trận, ta lưu trữ:

• Mỗi đỉnh (node) là một khóa (key) trong mảng.
• Các đỉnh kề (neighbor nodes) được lưu thành mảng con, đi kèm với trọng số (weight) của cạnh.

✅ 3. Dữ liệu mẫu:

$graph = [
    'A' => ['B' => 1, 'C' => 4],
    'B' => ['C' => 2, 'D' => 5],
    'C' => ['D' => 1],
    'D' => []
];

🔍 Giải thích:

• 'A' => ['B' => 1, 'C' => 4]: từ đỉnh A có thể đi đến:
  • B với trọng số là 1
  • C với trọng số là 4
• 'B' => ['C' => 2, 'D' => 5]: từ B đi được:
  • C với trọng số 2
  • D với trọng số 5
• 'C' => ['D' => 1]: từ C đi được D với trọng số 1
• 'D' => []: từ D không đi đâu được nữa (nút lá)

🔁 Tổng kết:

Đây là đồ thị có hướng, vì ví dụ A → B không có nghĩa là B → A.