Đồ thị là gì?

Đồ thị là một cấu trúc dữ liệu mô hình hóa một tập hợp đối tượng và các kết nối giữa chúng. Các đối tượng được gọi là đỉnh (hoặc nút), còn các kết nối được gọi là cạnh.

Đồ thị có mặt ở khắp nơi. Mạng xã hội là đồ thị (con người là đỉnh, tình bạn là cạnh). Bản đồ đường sá là đồ thị (giao lộ là đỉnh, đường phố là cạnh). Internet, cây phụ thuộc và bản đồ trò chơi đều là đồ thị.

Trong khóa học này, chúng ta tập trung vào đồ thị vô hướng: nếu một cạnh nối u và v, thì v cũng được nối với u. Đồ thị không có hướng. Chúng ta sẽ dùng số nguyên làm khóa của các đỉnh để mọi thứ đơn giản hơn.

Bên trong, chúng ta sẽ lưu đồ thị dưới dạng danh sách kề: một ánh xạ từ mỗi đỉnh đến danh sách các đỉnh kề với nó. Cách này giúp tìm các đỉnh kề của một đỉnh chỉ bằng một lần truy cập vào ánh xạ, đúng với nhu cầu của hầu hết các thuật toán đồ thị.

Các thao tác chúng ta sẽ xây dựng cho lớp Graph gồm:

1. addVertex: Thêm một đỉnh mới chưa có cạnh nào.
2. addEdge: Nối hai đỉnh.
3. hasEdge: Kiểm tra xem hai đỉnh có được nối với nhau hay không.
4. getNeighbors: Lấy danh sách các đỉnh kề với một đỉnh.
5. removeEdge: Ngắt kết nối giữa hai đỉnh.
6. size: Đếm số đỉnh trong đồ thị.

Cùng xây dựng lớp Graph nhé!