Biểu đồ là 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 kết nối bằng các liên kết. Các đối tượng được kết nối với nhau được biểu thị bằng các điểm được gọi là các đỉnh và các liên kết kết nối các đỉnh được gọi là các cạnh .
Chính thức, đồ thị là một cặp tập hợp (V, E) , trong đó V là tập hợp các đỉnh và E là tập hợp các cạnh, nối các cặp đỉnh. Hãy nhìn vào 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 đồ thị
Đồ 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 các cạnh hai chiều. Trước khi chúng ta tiến xa hơn, hãy làm quen với một số điều khoản quan trọng -
- Vertex - Mỗi nút của biểu đồ đượ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 cách sử dụng một mảng như trong hình dưới đây. Ở đây A có thể được xác định bởi chỉ số 0. B có thể được xác định bằng chỉ số 1, v.v.
- Cạnh - Cạnh thể hiện một đường dẫn giữa hai đỉnh hoặc một đườ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 dưới đây. Ở đâ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 đỉnh liền kề nhau nếu chúng được kết nối với nhau thông qua một cạnh. Trong ví dụ sau, B liền kề với A, C liền kề với B, v.v.
- Đường dẫn - Đường dẫn biểu thị một chuỗi các cạnh giữa hai đỉnh. Trong ví dụ sau, ABCD biểu thị đường dẫn 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ị -
- Thêm Vertex - Thêm một đỉnh vào biểu đồ.
- Thêm cạnh - Thêm một cạnh giữa hai đỉnh của đồ thị.
- Hiển thị Vertex - Hiển thị một đỉnh của biểu đồ.
Được cập nhật: hôm qua lúc 19:25:38 | Lượt xem: 524
