Tóm tắt¶

Điểm lại trọng tâm¶

Đồ thị gồm các đỉnh và cạnh, có thể được biểu diễn dưới dạng một tập hợp các đỉnh và một tập hợp các cạnh.
So với quan hệ tuyến tính được mô hình hóa bởi danh sách liên kết và quan hệ chia để trị được mô hình hóa bởi cây, quan hệ dạng mạng được mô hình hóa bởi đồ thị mang lại tính linh hoạt cao hơn nhiều và do đó cũng phức tạp hơn.
Trong đồ thị có hướng, các cạnh có hướng; trong đồ thị liên thông, mọi đỉnh đều có thể đi tới từ bất kỳ đỉnh nào khác; và trong đồ thị có trọng số, mỗi cạnh đều mang một trọng số.
Ma trận kề sử dụng ma trận để biểu diễn đồ thị, trong đó mỗi hàng (cột) đại diện cho một đỉnh, và các phần tử ma trận đại diện cho các cạnh, sử dụng \(1\) hoặc \(0\) để biểu thị việc giữa hai đỉnh có cạnh nối hay không. Ma trận kề cực kỳ hiệu quả đối với các thao tác thêm, xóa, tra cứu và sửa đổi, nhưng tiêu tốn nhiều không gian lưu trữ.
Danh sách kề sử dụng nhiều danh sách liên kết để biểu diễn đồ thị: danh sách liên kết thứ \(i\) tương ứng với đỉnh \(i\) và lưu trữ tất cả các đỉnh kề với nó. So với ma trận kề, danh sách kề tiết kiệm không gian hơn, nhưng thao tác tra cứu cạnh kém hiệu quả hơn vì phải duyệt danh sách liên kết.
Khi các danh sách liên kết trong danh sách kề trở nên quá dài, chúng có thể được chuyển đổi thành cây đỏ-đen hoặc bảng băm, từ đó cải thiện hiệu suất tra cứu.
Dưới góc độ thuật toán, ma trận kề thể hiện tư tưởng "đánh đổi không gian lấy thời gian", trong khi danh sách kề thể hiện tư tưởng "đánh đổi thời gian lấy không gian".
Đồ thị có thể được sử dụng để mô hình hóa nhiều hệ thống thực tế khác nhau, chẳng hạn như mạng xã hội và các tuyến tàu điện ngầm.
Cây là trường hợp đặc biệt của đồ thị, và duyệt cây là trường hợp đặc biệt của duyệt đồ thị.
Tìm kiếm theo chiều rộng trong đồ thị khám phá từ gần đến xa, mở rộng theo từng lớp, và thường được triển khai bằng hàng đợi.
Tìm kiếm theo chiều sâu trong đồ thị đi theo một đường đi sâu nhất có thể và quay lui khi không thể đi xa hơn, và thường được triển khai bằng đệ quy.

Q & A¶

Q: Đường đi được định nghĩa là một chuỗi các đỉnh hay một chuỗi các cạnh?

Định nghĩa trên các phiên bản ngôn ngữ khác nhau của Wikipedia là không nhất quán: phiên bản tiếng Anh viết "đường đi là một chuỗi các cạnh", trong khi phiên bản tiếng Trung viết "đường đi là một chuỗi các đỉnh". Sau đây là đoạn văn bản gốc tiếng Anh: In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices.

Trong tài liệu này, đường đi được coi là một chuỗi các cạnh chứ không phải chuỗi các đỉnh. Điều này là do có thể có nhiều cạnh kết nối giữa hai đỉnh, và khi đó mỗi cạnh sẽ tương ứng với một đường đi.

Q: Trong đồ thị không liên thông, liệu có tồn tại các đỉnh không thể đi tới không?

Trong đồ thị không liên thông, nếu bắt đầu từ một đỉnh cụ thể, sẽ có ít nhất một đỉnh khác không thể tiếp cận được. Để duyệt qua đồ thị không liên thông, bạn cần nhiều điểm xuất phát để có thể bao phủ tất cả các thành phần liên thông.

Q: Trong danh sách kề, các đỉnh kề với một đỉnh cho trước có yêu cầu gì về mặt thứ tự không?

Chúng có thể xuất hiện theo bất kỳ thứ tự nào. Tuy nhiên trong thực tế, chúng có thể cần được sắp xếp theo các quy tắc cụ thể, chẳng hạn như thứ tự thêm các đỉnh hoặc thứ tự giá trị của đỉnh, điều này giúp ích khi cần tìm nhanh một đỉnh có giá trị cực trị nào đó.