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

Đồ thị là một khái niệm quan trọng trong khoa học máy tính. Chúng ta thường gặp đồ thị trong các bài toán về mạng, tối ưu, và nhiều lĩnh vực khác. Để làm việc với đồ thị trên máy tính, chúng ta cần biết cách biểu diễn nó một cách hiệu quả.

Ma trận kề

Một cách phổ biến để biểu diễn đồ thị trên máy tính là sử dụng ma trận kề. Ma trận kề là một ma trận vuông kích thước N×N, trong đó N là số đỉnh của đồ thị.

Bạn đang xem: Biểu diễn đồ thị trên máy tính

• Phần tử adj[u][v] của ma trận kề có giá trị x nếu có một cạnh nối từ đỉnh u đến đỉnh v.
• Phần tử adj[u][u] có thể có giá trị tùy ý, thường là 0.

Ma trận kề có những ưu điểm sau:

• Đơn giản, dễ cài đặt.
• Dễ kiểm tra xem hai đỉnh u và v có kề nhau hay không.

Tuy nhiên, ma trận kề cũng có nhược điểm. Nó tiêu tốn nhiều ô nhớ và đòi hỏi duyệt qua nhiều đỉnh để xác định các đỉnh kề với một đỉnh khác.

Danh sách cạnh

Một cách biểu diễn khác là sử dụng danh sách cạnh. Danh sách cạnh là một danh sách lưu trữ các cạnh của đồ thị.

• Mỗi cạnh (u,v) được biểu diễn bằng một cặp (u,v).

Danh sách cạnh có những ưu điểm sau:

• Tiết kiệm không gian lưu trữ, đặc biệt khi đồ thị có ít cạnh.
• Dễ dàng duyệt qua các cạnh trong một giải thuật cụ thể.

Tuy nhiên, danh sách cạnh cũng có nhược điểm là tốn thời gian khi cần xét tất cả các cạnh liên quan đến một đỉnh.

Danh sách kề

Xem thêm : Bài tập tình huống Luật doanh nghiệp 2020

Một cách biểu diễn phổ biến khác là sử dụng danh sách kề. Danh sách kề là một danh sách lưu trữ các đỉnh kề với một đỉnh khác.

• Với mỗi đỉnh u, ta tạo một danh sách adj[u] chứa các đỉnh kề với u.

Danh sách kề có những ưu điểm sau:

• Dễ dàng duyệt qua các đỉnh kề và các cạnh của đồ thị.
• Tiết kiệm không gian lưu trữ.

Tuy nhiên, để kiểm tra xem hai đỉnh u và v có kề nhau hay không, chúng ta phải duyệt qua toàn bộ danh sách kề của u hoặc v.

Trong các bài toán đồ thị, chúng ta thường sử dụng danh sách kề vì nó kết hợp được các ưu điểm của ma trận kề và danh sách cạnh.

Ảnh minh họa:

Ưu điểm và nhược điểm

Ma trận kề có những ưu điểm và nhược điểm sau:

Xem thêm : Tin tức

Ưu điểm:

• Đơn giản, dễ cài đặt.
• Kiểm tra hai đỉnh u và v có kề nhau hay không nhanh chóng.

Nhược điểm:

• Tiêu tốn nhiều ô nhớ.
• Để xét một đỉnh u kề với những đỉnh nào, phải duyệt toàn bộ các đỉnh v và kiểm tra điều kiện.

Danh sách cạnh có những ưu điểm và nhược điểm sau:

Xem thêm : Tin tức

Ưu điểm:

• Tiết kiệm không gian lưu trữ.
• Duyệt cạnh dễ dàng trong một số trường hợp đặc biệt.

Nhược điểm:

• Khi cần xét tất cả các cạnh của đồ thị, đòi hỏi thời gian nếu đồ thị có nhiều cạnh.

Danh sách kề có những ưu điểm và nhược điểm sau:

Xem thêm : Tin tức

Ưu điểm:

• Duyệt đỉnh kề và các cạnh của đồ thị nhanh chóng.
• Tiết kiệm không gian lưu trữ.

Nhược điểm:

• Khi cần kiểm tra một cạnh (u,v) có phải là một cạnh của đồ thị hay không, phải duyệt toàn bộ danh sách kề của u hoặc v.

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về cách biểu diễn đồ thị trên máy tính bằng ma trận kề, danh sách cạnh, và danh sách kề. Mỗi cách biểu diễn có ưu điểm và nhược điểm riêng. Tùy thuộc vào yêu cầu của bài toán, chúng ta có thể lựa chọn cách biểu diễn phù hợp nhất.

Nguồn tham khảo:

• Sách Giải thuật và Lập trình – thầy Lê Minh Hoàng.
• Tài liệu giáo khoa chuyên Tin quyển 1 – thầy Hồ Sĩ Đàm.

©️ Tác giả: Vũ Quế Lâm từ Viblo

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập