Cấu trúc dữ liệu - Cấu trúc dữ liệu biểu đồ
Đồ thị là một biểu diễn bằng hình ảnh của một tập hợp các đối tượng trong đó một số cặp đối tượng được nối với nhau bằng các liên kết. Các đối tượng được kết nối với nhau được biểu diễn bằng các điểm được gọi làverticesvà các liên kết nối các đỉnh được gọi là edges.
Về mặt hình thức, biểu đồ là một cặp tập hợp (V, E), Ở đâu V là tập hợp các đỉnh và Elà tập hợp các cạnh, nối các cặp đỉnh. Hãy xem biểu đồ sau:
Trong biểu đồ trên,
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Cấu trúc dữ liệu biểu đồ
Đồ thị toán học có thể được biểu diễn trong cấu trúc dữ liệu. Chúng ta có thể biểu diễn một đồ thị bằng cách sử dụng một mảng các đỉnh và một mảng hai chiều các cạnh. Trước khi tiếp tục, chúng ta hãy tự làm quen với một số thuật ngữ quan trọng -
Vertex- Mỗi nút của đồ thị được biểu diễn dưới dạng một đỉnh. Trong ví dụ sau, vòng tròn được dán nhãn đại diện cho các đỉnh. Do đó, A đến G là các đỉnh. Chúng ta có thể biểu diễn chúng bằng một mảng như trong hình sau. Ở đây A có thể được xác định bằng chỉ số 0. B có thể được xác định bằng cách sử dụng chỉ số 1, v.v.
Edge- Cạnh biểu diễn đường đi giữa hai đỉnh hoặc đường thẳng giữa hai đỉnh. Trong ví dụ sau, các dòng từ A đến B, B đến C, v.v. đại diện cho các cạnh. Chúng ta có thể sử dụng một mảng hai chiều để biểu diễn một mảng như trong hình sau. Ở đây AB có thể được biểu diễn là 1 ở hàng 0, cột 1, BC là 1 ở hàng 1, cột 2, v.v., giữ các kết hợp khác là 0.
Adjacency- Hai nút hoặc hai đỉnh kề nhau nếu chúng được nối với nhau qua một cạnh. Trong ví dụ sau, B là liền kề với A, C là liền kề với B, v.v.
Path- Đường đi biểu diễn một dãy các cạnh giữa hai đỉnh. Trong ví dụ sau, ABCD biểu diễn một đường đi từ A đến D.
Hoạt động cơ bản
Sau đây là các hoạt động chính cơ bản của Đồ thị:
Add Vertex - Thêm một đỉnh vào đồ thị.
Add Edge - Thêm một cạnh giữa hai đỉnh của đồ thị.
Display Vertex - Hiển thị một đỉnh của đồ thị.
Để biết thêm về Đồ thị, vui lòng đọc Hướng dẫn Lý thuyết Đồ thị . Chúng ta sẽ tìm hiểu về việc duyệt qua một biểu đồ trong các chương tới.