Danh sách kề và biểu diễn ma trận của đồ thị

Bởi: Sarah Chen Sarah Chen
Hours cập nhật

Mặc dù trông chúng có vẻ khác nhau nhưng tất cả các loại đồ thị có thể được biểu diễn theo cách tương tự. Nhìn chung có hai loại Biểu diễn đồ thị:

  1. Ma trận kề
  2. Danh sách gần kề

Danh sách gần kề

Danh sách kề bao gồm các danh sách liên kết. Mỗi đỉnh được coi là một chỉ mục mảng và mỗi phần tử đại diện cho một danh sách liên kết. Các danh sách liên kết này chứa các đỉnh có các cạnh bằng đỉnh chỉ mục.

Dưới đây là ví dụ về danh sách kề:

Danh sách gần kề

Giả sử một đồ thị chứa V số đỉnh và E số cạnh.

Nhìn chung, độ phức tạp của không gian sẽ là O(V + E).

Độ phức tạp của không gian trường hợp xấu nhất sẽ là O(V2) nếu đồ thị đã cho là đồ thị hoàn chỉnh

Ma trận kề

Ma trận kề bao gồm một mảng 2D. Đồ thị có số đỉnh là V thì kích thước của ma trận sẽ là VxV.

Nói, matrix[i][j] = 5. Điều đó có nghĩa là có một cạnh giữa nút i và j với trọng số là 5.

Chúng ta hãy xem Đồ thị sau và Ma trận kề của nó:

Ma trận kề

Chúng tôi đã tạo ra mảng 2D bằng cách sử dụng các bước sau:

Bước 1) Đỉnh A có cạnh trực tiếp với B và trọng số là 5. Vì vậy, ô ở hàng A và cột B sẽ được điền bằng 5. Các ô còn lại ở hàng A sẽ được điền bằng XNUMX.

Bước 2) Đỉnh B có cạnh trực tiếp với C và trọng số là 4. Vì vậy, ô ở hàng B và cột C sẽ được điền bằng 4. Các ô còn lại ở hàng B sẽ được điền bằng XNUMX vì B không có cạnh nào đi tới bất kỳ cạnh nào các nút khác.

Bước 3) Đỉnh C không có cạnh trực tiếp với bất kỳ đỉnh nào khác. Vì vậy, hàng C sẽ chứa đầy số không.

Bước 4) Đỉnh D có cạnh định hướng với A và C.

  • Ở đây, ô ở hàng D và cột A sẽ có giá trị là 7. Các ô ở hàng D và cột C sẽ có giá trị là 2.
  • Các ô còn lại ở hàng D sẽ được điền bằng số 0.

Bước 5) Đỉnh E có cạnh định hướng bằng B và D. Ô ở hàng E và cột B sẽ có giá trị là 6. Các ô ở hàng E và cột D sẽ có giá trị là 3. Các ô còn lại ở hàng D sẽ là chứa đầy số không.

Dưới đây là một số điểm cần chú ý:

  • Đồ thị không có vòng tự lặp khi đường chéo chính của ma trận kề bằng 0.
  • Đồ thị là đồ thị có hướng nếu các chỉ số (a, b) và (b, a) không có cùng giá trị. Nếu không, Đồ thị là đồ thị có hướng.
  • Biểu đồ sẽ là biểu đồ có trọng số nếu giá trị của các ô lớn hơn 1.

Có một số vấn đề với ma trận kề vì nó yêu cầu các khoảng trống bình phương. Ở đây, chúng ta đang lưu trữ các cạnh không được kết nối. Các cạnh này phân bổ không gian trong bộ nhớ.

Ví dụ: nếu chúng ta có một biểu đồ có 100 nút thì cần 10 nghìn ô để lưu trữ nó trong RAM. Với ít cạnh hơn trong Đồ thị, việc phân bổ bộ nhớ lớn như vậy có thể là lãng phí. Vì vậy, độ phức tạp không gian sử dụng Ma trận kề sẽ là O(N2), trong đó N có nghĩa là số nút trong Biểu đồ.