Biểu diễn đồ thị

6.1 Ma trận kề: nguyên lý hoạt động, ưu và nhược điểm.

Ma trận kề là một cách biểu diễn đồ thị dưới dạng ma trận vuông kích thước n x n, nơi n là số lượng đỉnh trong đồ thị. Các phần tử của ma trận chỉ ra sự tồn tại hay không tồn tại của cạnh giữa các đỉnh:

• Nếu tồn tại cạnh giữa các đỉnh i và j, thì phần tử A[i][j] = 1 (hoặc trọng số của cạnh nếu đồ thị có trọng số).
• Nếu không có cạnh, thì A[i][j] = 0.

Ví dụ:

Đối với đồ thị với các đỉnh A, B, C và các cạnh (A, B), (B, C) và (C, A), ma trận kề sẽ là:

Nếu tất cả các đỉnh đều được kết nối với tất cả, thì ma trận kề sẽ trông như thế này:

Ưu điểm:

• Đơn giản: dễ hiểu và thực hiện.
• Truy cập nhanh: kiểm tra sự tồn tại của cạnh giữa hai đỉnh thực hiện trong O(1).
• Phù hợp với đồ thị dày đặc: hiệu quả cho đồ thị có số lượng lớn các cạnh.

Nhược điểm:

• Tốn kém bộ nhớ cao: yêu cầu bộ nhớ O(n^2), ngay cả khi đồ thị chứa ít cạnh (đồ thị mỏng).
• Không hiệu quả đối với đồ thị mỏng: khi có nhiều đỉnh và ít cạnh, hầu hết các phần tử của ma trận sẽ là số không, dẫn đến việc sử dụng bộ nhớ không hiệu quả.

6.2 Danh sách kề: nguyên lý hoạt động, ưu và nhược điểm.

Danh sách kề là một cách biểu diễn đồ thị dưới dạng mảng của danh sách. Mỗi phần tử của mảng tương ứng với một đỉnh của đồ thị và chứa danh sách tất cả các đỉnh kề với nó.

Ví dụ:

Đối với đồ thị với các đỉnh A, B, C và các cạnh (A, B), (B, C) và (C, A), danh sách kề sẽ là:

Nếu tất cả các đỉnh đều được kết nối với tất cả, thì danh sách kề sẽ trông như thế này:

Ưu điểm:

• Sử dụng bộ nhớ hiệu quả: yêu cầu bộ nhớ O(V + E), nơi V là số lượng đỉnh, E là số lượng cạnh, làm cho nó phù hợp hơn với đồ thị mỏng.
• Dễ dàng duyệt: thuận tiện cho việc thực hiện các thao tác duyệt đồ thị (ví dụ: tìm kiếm theo chiều rộng hoặc chiều sâu).

Nhược điểm:

• Truy cập phức tạp hơn: kiểm tra sự tồn tại của cạnh giữa hai đỉnh yêu cầu thời gian O(k), nơi k là số lượng hàng xóm của đỉnh.
• Cấu trúc ít rõ ràng hơn: khó thực hiện và hiểu hơn so với ma trận kề.

6.3 So sánh các phương pháp khác nhau để biểu diễn đồ thị.

Hãy so sánh các phương pháp khác nhau để biểu diễn đồ thị.

1. Ma trận kề:

• Đơn giản: dễ hiểu và thực hiện.
• Bộ nhớ: yêu cầu bộ nhớ O(n^2), có thể không hiệu quả cho đồ thị mỏng.
• Tốc độ truy cập: kiểm tra sự tồn tại của cạnh thực hiện trong O(1).
• Phù hợp: cho đồ thị dày đặc với số lượng lớn các cạnh.

2. Danh sách kề:

• Đơn giản: ít rõ ràng hơn so với ma trận kề, nhưng vẫn dễ hiểu.
• Bộ nhớ: yêu cầu bộ nhớ O(V + E), hiệu quả hơn cho đồ thị mỏng.
• Tốc độ truy cập: kiểm tra sự tồn tại của cạnh thực hiện trong O(k), nơi k là số lượng hàng xóm của đỉnh.
• Phù hợp: cho đồ thị mỏng với số lượng ít các cạnh.

So sánh:

Ma trận kề phù hợp hơn cho đồ thị dày đặc, nơi hầu hết các đỉnh được kết nối bởi các cạnh, vì nó đảm bảo truy cập nhanh tới thông tin về các cạnh và dễ thực hiện.

Danh sách kề thích hợp hơn cho đồ thị mỏng, nơi số lượng cạnh nhỏ hơn nhiều so với số lượng cặp đỉnh có thể có. Chúng đảm bảo sử dụng bộ nhớ hiệu quả và thuận tiện cho việc thực hiện các thao tác duyệt đồ thị.