Cấu trúc dữ liệu đồ thị và Algorithms (Thí dụ)

Biểu đồ trong cấu trúc dữ liệu là gì?

Đồ thị là một cấu trúc dữ liệu phi tuyến tính bao gồm các đỉnh và cạnh, trong đó các đỉnh chứa thông tin hoặc dữ liệu, và các cạnh đóng vai trò là liên kết giữa một cặp đỉnh.

Nó được sử dụng để giải quyết các vấn đề thực tế như tìm tuyến đường tốt nhất đến địa điểm đích và tuyến đường cho mạng viễn thông và mạng xã hội. Người dùng được coi là một nút trong đồ thị, và các đường dây là các cạnh kết nối người dùng.

Nếu các cạnh được biểu diễn dưới dạng E và các đỉnh được biểu diễn dưới dạng V thì đồ thị G có thể được viết dưới dạng tập hợp các đỉnh và cạnh, chẳng hạn như G (V, E).

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

Dưới đây là một ví dụ đơn giản về cấu trúc dữ liệu đồ thị:

Đây là một đồ thị vô hướng đơn giản (một loại đồ thị). Tập hợp các đỉnh là: {A, B, C, D, E, F}. Hai đỉnh tạo thành một cạnh. Ví dụ, A và B được nối với nhau bằng một cạnh. Tuy nhiên, A và F không được nối với nhau bằng bất kỳ cạnh nào.

Thuật ngữ đồ thị trong cấu trúc dữ liệu

Sau đây là một số thuật ngữ quan trọng được sử dụng trong cấu trúc dữ liệu đồ thị:

Hạn	Mô tả Chi tiết
đỉnh đầu	Mỗi phần tử dữ liệu được gọi là một đỉnh hoặc một nút. Trong hình ảnh trên, A, B, C, D và E là các đỉnh.
Cạnh (Cung)	Đường nối giữa hai nút hoặc đỉnh được gọi là cạnh (cung). Cạnh có hai đầu và được biểu diễn dưới dạng (đỉnh bắt đầu, đỉnh kết thúc).
Cạnh vô hướng	Đó là một cạnh hai chiều.
Biên hướng	Đó là một cạnh một chiều.
Cạnh có trọng số	Một cạnh có giá trị được ghi trên đó.
Bằng cấp	Trong đồ thị, số cạnh nối với một đỉnh được gọi là bậc của đỉnh.
Bằng cấp	Tổng số cạnh đến được kết nối với một đỉnh.
Bằng cấp cao hơn	Tổng số cạnh đi được kết nối với một đỉnh.
Tự vòng lặp	Một cạnh được gọi là tự lặp nếu hai điểm cuối của nó trùng nhau.
Sự gần gũi	Các đỉnh được gọi là kề nhau nếu có một cạnh nối giữa chúng.

Các loại đồ thị trong cấu trúc dữ liệu

Dưới đây là danh sách phổ biến nhất các loại đồ thị trong cấu trúc dữ liệu:

• Đồ thị có hướng
• Đồ thị vô hướng
• Biểu đồ có trọng số
• Đồ thị hai chiều
• Đồ thị vô hạn
• Đồ thị rỗng
• Đồ thị tầm thường
• Đa đồ thị
• Đồ thị hoàn chỉnh
• Đồ thị được kết nối
• Đồ thị tuần hoàn
• Đồ thị vòng có hướng (DAG)
• Đồ thị chu kỳ
• Đồ thị hai bên
• Đồ thị Euler
• Đồ thị Hamilton

Làm thế nào để biểu diễn đồ thị trong cấu trúc dữ liệu?

Đồ thị thường được lưu trữ trong bộ nhớ bằng một trong hai cách biểu diễn. Việc lựa chọn cách biểu diễn này ảnh hưởng đến lượng bộ nhớ mà đồ thị sử dụng và tốc độ thực thi các thao tác thông thường.

• Ma trận kề: Một mảng V × V hai chiều trong đó ô [i][j] là 1 (hoặc trọng số cạnh) nếu tồn tại cạnh giữa đỉnh i và đỉnh j, và 0 nếu không. Nó cho phép tra cứu cạnh O(1) nhưng sử dụng không gian O(V²), do đó phù hợp nhất cho đồ thị dày đặc.
• Danh sách lân cận: Một mảng các danh sách, trong đó mỗi đỉnh lưu trữ một danh sách các đỉnh lân cận của nó. Nó sử dụng không gian O(V + E) và hiệu quả đối với các đồ thị thưa, đó là lý do tại sao hầu hết các đồ thị thực tế đều sử dụng nó.

Bạn có thể tìm hiểu thêm về những điều này trong phần tiếp theo. danh sách kề và biểu diễn ma trận của đồ thị hướng dẫn.

Ứng dụng của cấu trúc dữ liệu đồ thị

Đồ thị có rất nhiều ứng dụng. Có rất nhiều thuật toán sử dụng đồ thị. Dưới đây là một số ứng dụng của đồ thị:

• Google Bản đồ sử dụng đồ thị để tìm giao điểm của hai con đường và tính khoảng cách giữa hai địa điểm. Ví dụ: dijkstraDùng để tìm khoảng cách ngắn nhất giữa điểm xuất phát và điểm đến.
• Facebook sử dụng đồ thị để tìm bạn bè chung của người dùng. Thuật toán của nó coi mỗi người dùng như một nút của đồ thị.
• Để phân bổ tài nguyên, người ta sử dụng đồ thị có hướng không chu trình (DAG). Đồ thị này kiểm tra sự phụ thuộc lẫn nhau giữa các tài nguyên.
• Google Công cụ tìm kiếm sử dụng đồ thị để tạo ra thứ hạng cho các trang web.
• Bản đồping Thiết bị sử dụng cấu trúc dữ liệu đồ thị.
• A bộ định tuyến và giao thức của nó sử dụng đồ thị để tìm ra đường đi đến đích.

Câu Hỏi Thường Gặp