Cấu trúc dữ liệu biểu đồ

Mục lục

Thuật ngữ đồ thị
Biểu diễn đồ thị
Hoạt động đồ thị

Trong hướng dẫn này, bạn sẽ tìm hiểu Cấu trúc Dữ liệu Đồ thị là gì. Ngoài ra, bạn sẽ tìm thấy các đại diện của một đồ thị.

Cấu trúc dữ liệu đồ thị là một tập hợp các nút có dữ liệu và được kết nối với các nút khác.

Hãy cố gắng hiểu điều này thông qua một ví dụ. Trên facebook, mọi thứ đều là một nút. Điều đó bao gồm Người dùng, Ảnh, Album, Sự kiện, Nhóm, Trang, Bình luận, Câu chuyện, Video, Liên kết, Ghi chú… bất cứ thứ gì có dữ liệu là một nút.

Mọi mối quan hệ là một cạnh từ nút này sang nút khác. Cho dù bạn đăng ảnh, tham gia nhóm, thích một trang, v.v., một lợi thế mới sẽ được tạo ra cho mối quan hệ đó.

Ví dụ về cấu trúc dữ liệu đồ thị

Tất cả facebook sau đó là một tập hợp các nút và cạnh này. Điều này là do facebook sử dụng cấu trúc dữ liệu đồ thị để lưu trữ dữ liệu của nó.

Chính xác hơn, biểu đồ là một cấu trúc dữ liệu (V, E) bao gồm

Tập hợp các đỉnh V
Tập hợp các cạnh E, được biểu diễn dưới dạng các cặp đỉnh có thứ tự (u, v)

Dọc và cạnh

Trong biểu đồ,

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Thuật ngữ đồ thị

Liền kề : Một đỉnh được cho là kề với một đỉnh khác nếu có một cạnh nối chúng. Các đỉnh 2 và 3 không liền nhau vì không có cạnh nào giữa chúng.
Đường dẫn : Một dãy các cạnh cho phép bạn đi từ đỉnh A đến đỉnh B được gọi là đường dẫn. 0-1, 1-2 và 0-2 là các đường đi từ đỉnh 0 đến đỉnh 2.
Đồ thị có hướng : Một đồ thị trong đó cạnh (u, v) không nhất thiết có nghĩa là cũng có cạnh (v, u). Các cạnh trong biểu đồ như vậy được biểu diễn bằng các mũi tên để chỉ hướng của cạnh.

Biểu diễn đồ thị

Đồ thị thường được biểu diễn theo hai cách:

1. Ma trận gần kề

Ma trận kề là một mảng 2D gồm các đỉnh V x V. Mỗi hàng và cột đại diện cho một đỉnh.

Nếu giá trị của bất kỳ phần tử nào a(i)(j)là 1, nó thể hiện rằng có một cạnh nối đỉnh i và đỉnh j.

Ma trận kề cho biểu đồ chúng tôi đã tạo ở trên là

Đồ thị ma trận kề

Vì là đồ thị vô hướng nên đối với cạnh (0,2), chúng ta cũng cần đánh dấu cạnh (2,0); làm cho ma trận kề đối xứng qua đường chéo.

Việc tra cứu cạnh (kiểm tra xem có tồn tại một cạnh giữa đỉnh A và đỉnh B hay không) là cực kỳ nhanh chóng trong biểu diễn ma trận kề nhưng chúng ta phải dành không gian cho mọi liên kết có thể có giữa tất cả các đỉnh (V x V), vì vậy nó đòi hỏi nhiều không gian hơn.

2. Danh sách gần kề

Danh sách kề biểu thị một biểu đồ dưới dạng một mảng các danh sách được liên kết.

Chỉ số của mảng đại diện cho một đỉnh và mỗi phần tử trong danh sách liên kết của nó đại diện cho các đỉnh khác tạo thành một cạnh với đỉnh.

Danh sách kề cho biểu đồ mà chúng tôi đã tạo trong ví dụ đầu tiên như sau:

Biểu diễn danh sách gần kề

Danh sách kề là hiệu quả về mặt lưu trữ vì chúng ta chỉ cần lưu trữ các giá trị cho các cạnh. Đối với một biểu đồ có hàng triệu đỉnh, điều này có nghĩa là rất nhiều không gian được tiết kiệm.