Biểu diễn đồ thị trong máy tính

1. MA TRẬN KỀ (ADJACENCY MATRIX)

  • Ma trận kề là một trong 3 cách biểu diễn đồ thị, với các ưu điểm là trực quan dễ cài đặt và làm việc.
  • G = (V, E) là một đơn đồ thị, không mất tính tổng quát có thể coi các đỉnh được đánh số 1, 2, …, n. Khi đó ta có thể biểu diễn đồ thị bằng một ma trận vuông Matrix cấp n
  • Matrix[i, i] = 0
  • Matrix[i, j] = 1 nếu (i, j) ∈ E, i≠j
  • Matrix[i, j] = 0 nếu (i, j) ∉ E, i≠j

 

2. DANH SÁCH KỀ.(ADJACENCY LIST)

  • Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị, ta cho tương ứng với nó một danh sách các đỉnh kề với v.
  • Danh sách cạnh với ưu điểm tiết kiệm bộ nhớ hơn, dễ dàng duyệt thêm bớt các đỉnh các cạnh nên hay được lựa chọn để biểu diễn đồ thị.

 

 

 

The following two tabs change content below.

phuongtn