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

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

Biểu đồ là 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 hoạt động như một liên kết giữa các cặp đỉnh.

Nó được sử dụng để giải quyết các vấn đề thực tế như tìm đường đi tốt nhất đến vị trí đích và đường đi 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 Biểu đồ và các 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

Đây là một ví dụ đơn giản về cấu trúc dữ liệu biểu đồ:

Đó là một biểu đồ vô hướng đơn giản (một loại Biểu đồ). Ở đây 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 liên kết với một cạnh. Tuy nhiên, A và F không được liên kết với 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ả
đỉnh đầu	Tất cả phần tử dữ liệu được gọi là đỉnh hoặc nút. Trong hình trên, A, B, C, D & E là các đỉnh.
Cạnh (Cung)	Các liên kết kết nối giữa hai nút hoặc đỉnh được gọi là cạnh (Arc). Nó có hai đầu và được biểu diễn dưới dạng (startingVertex, endVertex).
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ị trên đó.
Bằng cấp	Trong đồ thị, số cạnh nối với một đỉnh được gọi là độ.
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à liền kề nếu một cạnh được nối.

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

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

Một biểu đồ có nhiều trường hợp sử dụng. Có rất nhiều thuật toán sử dụng đồ thị rất nhiều. Dưới đây là một số ứng dụng của Graph:

Google Maps sử dụng biểu đồ để 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ụ, dijkstra, để tìm khoảng cách ngắn nhất giữa vị trí nguồn và đích.
Facebook sử dụng Đồ thị để tìm bạn chung của người dùng. Thuật toán của nó coi mỗi người dùng là một nút của biểu đồ.
Để phân bổ tài nguyên, DAG (Biểu đồ tuần hoàn trực tiếp) được sử dụng. Nó kiểm tra sự phụ thuộc của các tài nguyên.
Công cụ tìm kiếm Google sử dụng biểu đồ để tạo thứ hạng cho các trang web.
Một thiết bị bản đồ sử dụng cấu trúc dữ liệu đồ thị.
bộ định tuyến và giao thức của t sử dụng Biểu đồ để tìm hiểu đường dẫn của đường dẫn đích.

Bạn có thể thích: