Tìm hiểu một số cách biểu diễn dữ liệu đồ thị trên máy tính. Thảo luận xem cách nào là hợp lí nhất. Hãy biểu diễn dữ liệu của các đồ thị ở Hình 11.12.

Có hai cách biểu diễn dữ liệu đồ thị trên máy tính mà bạn có thể xem xét:

• Ma trận kề: Mỗi hàng và cột tương ứng với một đỉnh, và giá trị tại hàng i, cột j là 1 nếu có cạnh nối giữa đỉnh i và j, ngược lại là 0.
• Danh sách kề: Mỗi đỉnh liệt kê các đỉnh mà nó kết nối trực tiếp.

Đồ thị (a) - Cấu trúc hình sao:

• Ma trận kề:

• Danh sách kề:
  • Đỉnh 0: 1, 2, 3, 4
  • Đỉnh 1: 0
  • Đỉnh 2: 0
  • Đỉnh 3: 0
  • Đỉnh 4: 0

Đồ thị (b) - Cấu trúc liên kết nhiều hơn:

• Ma trận kề:

• Danh sách kề:
  • Đỉnh 0: 1, 3
  • Đỉnh 1: 0, 2, 4
  • Đỉnh 2: 1, 3
  • Đỉnh 3: 0, 2, 4
  • Đỉnh 4: 1, 3