Đồ thị DSA
Đồ thị
Đồ thị là cấu trúc dữ liệu phi tuyến tính bao gồm các đỉnh (nút) và các cạnh.
Đỉnh hay còn gọi là nút là một điểm hoặc một đối tượng trong Đồ thị và một cạnh dùng để nối hai đỉnh với nhau.
Đồ thị không tuyến tính vì cấu trúc dữ liệu cho phép chúng ta có các đường dẫn khác nhau để đi từ đỉnh này sang đỉnh khác, không giống như các cấu trúc dữ liệu tuyến tính như Mảng hoặc Danh sách liên kết.
Đồ thị được sử dụng để biểu diễn và giải quyết các vấn đề trong đó dữ liệu bao gồm các đối tượng và mối quan hệ giữa chúng, chẳng hạn như:
- Mạng xã hội: Mỗi người là một đỉnh và các mối quan hệ (như tình bạn) là các cạnh. Thuật toán có thể gợi ý những người bạn tiềm năng.
- Bản đồ và Điều hướng: Các vị trí, như thị trấn hoặc điểm dừng xe buýt, được lưu dưới dạng các đỉnh và đường được lưu dưới dạng các cạnh. Thuật toán có thể tìm ra con đường ngắn nhất giữa hai vị trí khi được lưu trữ dưới dạng Biểu đồ.
- Internet: Có thể được biểu diễn dưới dạng Biểu đồ, với các trang web là các đỉnh và siêu liên kết là các cạnh.
- Sinh học: Đồ thị có thể mô hình hóa các hệ thống như mạng lưới thần kinh hoặc sự lây lan của bệnh tật.
Thuộc tính đồ thị
Sử dụng hoạt ảnh bên dưới để hiểu về các thuộc tính khác nhau của Biểu đồ và cách kết hợp các thuộc tính này.
Biểu đồ có trọng số là Biểu đồ trong đó các cạnh có giá trị. Giá trị trọng số của một cạnh có thể biểu thị những thứ như khoảng cách, sức chứa, thời gian hoặc xác suất.
Đồ thị được kết nối là khi tất cả các đỉnh được kết nối thông qua các cạnh bằng cách nào đó. Đồ thị không được kết nối là Đồ thị có các đồ thị con bị cô lập (rời rạc) hoặc các đỉnh cô lập đơn lẻ.
Đồ thị có hướng , còn được gọi là đồ thị ghép, là khi các cạnh giữa các cặp đỉnh có hướng. Hướng của một cạnh có thể biểu thị những thứ như thứ bậc hoặc dòng chảy.
Biểu đồ tuần hoàn được định nghĩa khác nhau tùy thuộc vào việc nó có được định hướng hay không:
- Đồ thị tuần hoàn có hướng là khi bạn có thể đi theo một đường dọc theo các cạnh có hướng đi theo vòng tròn. Việc loại bỏ cạnh có hướng từ F đến G trong hoạt ảnh ở trên làm cho Đồ thị có hướng không còn tuần hoàn nữa.
- Đồ thị tuần hoàn vô hướng là khi bạn có thể quay lại cùng một đỉnh mà bạn đã bắt đầu mà không cần sử dụng cùng một cạnh nhiều lần. Đồ thị vô hướng ở trên là đồ thị tuần hoàn vì chúng ta có thể bắt đầu và kết thúc ở đỉnh C mà không cần sử dụng cùng một cạnh hai lần.
Một vòng lặp , còn được gọi là vòng tự lặp, là một cạnh bắt đầu và kết thúc trên cùng một đỉnh. Vòng lặp là một chu trình chỉ bao gồm một cạnh. Bằng cách thêm vòng lặp trên đỉnh A trong hoạt ảnh ở trên, Biểu đồ sẽ trở thành tuần hoàn.
Biểu diễn đồ thị
Biểu diễn đồ thị cho chúng ta biết đồ thị được lưu trữ trong bộ nhớ như thế nào.
Các cách biểu diễn đồ thị khác nhau có thể:
- chiếm nhiều hay ít không gian.
- tìm kiếm hoặc thao tác nhanh hơn hoặc chậm hơn.
- sẽ phù hợp hơn tùy thuộc vào loại Biểu đồ mà chúng tôi có (có trọng số, được hướng dẫn, v.v.) và những gì chúng tôi muốn làm với Biểu đồ.
- dễ hiểu và dễ thực hiện hơn những cách khác.
Dưới đây là phần giới thiệu ngắn gọn về các cách biểu diễn Đồ thị khác nhau, nhưng Ma trận kề là cách biểu diễn mà chúng tôi sẽ sử dụng cho các Đồ thị trong phần tiếp theo của hướng dẫn này, vì nó dễ hiểu và dễ thực hiện cũng như hoạt động trong mọi trường hợp có liên quan đến hướng dẫn này.
Biểu diễn đồ thị lưu trữ thông tin về các đỉnh liền kề nhau và các cạnh giữa các đỉnh như thế nào. Biểu diễn đồ thị hơi khác một chút nếu các cạnh được định hướng hoặc có trọng số.
Hai đỉnh là kề nhau hoặc lân cận nếu có một cạnh giữa chúng.
Biểu diễn đồ thị ma trận kề
Ma trận kề là cách biểu diễn (cấu trúc) đồ thị mà chúng tôi sẽ sử dụng cho hướng dẫn này.
Cách triển khai Ma trận kề được hiển thị trên trang tiếp theo.
Ma trận kề là một mảng 2D (ma trận) trong đó mỗi ô trên chỉ mục (i,j) lưu trữ thông tin về cạnh từ đỉnh i đến đỉnh j .
Dưới đây là Biểu đồ có biểu diễn Ma trận kề bên cạnh.
và ma trận kề
Ma trận kề ở trên biểu thị một Đồ thị vô hướng, vì vậy các giá trị '1' chỉ cho chúng ta biết các cạnh ở đâu. Ngoài ra, các giá trị trong ma trận kề là đối xứng vì các cạnh đi cả hai chiều (Đồ thị vô hướng).
Để tạo Đồ thị có hướng với ma trận kề, chúng ta phải quyết định các cạnh đi từ và đến đỉnh nào bằng cách chèn giá trị vào đúng chỉ mục (i,j) . Để biểu diễn Biểu đồ có trọng số, chúng ta có thể đặt các giá trị khác ngoài '1' bên trong ma trận kề.
Dưới đây là Biểu đồ có hướng và có trọng số với biểu diễn Ma trận kề bên cạnh.
và ma trận kề của nó.
Trong ma trận kề trên, giá trị 3 của chỉ số (0,1) cho ta biết có một cạnh từ đỉnh A đến đỉnh B và trọng số của cạnh đó là 3 .
Như bạn có thể thấy, các trọng số được đặt trực tiếp vào ma trận kề cho cạnh chính xác và đối với Đồ thị có hướng, ma trận kề không nhất thiết phải đối xứng.
Biểu diễn đồ thị danh sách kề
Trong trường hợp chúng ta có Đồ thị 'thưa thớt' với nhiều đỉnh, chúng ta có thể tiết kiệm dung lượng bằng cách sử dụng Danh sách kề so với việc sử dụng Ma trận kề, vì Ma trận kề sẽ dành nhiều bộ nhớ trên các phần tử Mảng trống cho các cạnh không tồn tại .
Biểu đồ 'thưa thớt' là Biểu đồ trong đó mỗi đỉnh chỉ có các cạnh với một phần nhỏ của các đỉnh khác trong Biểu đồ.
Danh sách kề có một mảng chứa tất cả các đỉnh trong Biểu đồ và mỗi đỉnh có một Danh sách liên kết (hoặc Mảng) với các cạnh của đỉnh đó.
và danh sách kề của nó.
Trong danh sách kề ở trên, các đỉnh từ A đến D được đặt trong một mảng và mỗi đỉnh trong mảng có chỉ số được viết ngay bên cạnh.
Mỗi đỉnh trong Mảng có một con trỏ tới Danh sách liên kết đại diện cho các cạnh của đỉnh đó. Cụ thể hơn, Danh sách liên kết chứa các chỉ mục cho các đỉnh (láng giềng) liền kề.
Vì vậy, ví dụ, đỉnh A có liên kết đến Danh sách liên kết với các giá trị 3, 1 và 2. Các giá trị này là chỉ mục cho các đỉnh D, B và C liền kề của A.
Danh sách kề cũng có thể biểu thị Biểu đồ có hướng và có trọng số, như sau:
và danh sách kề của nó.
Trong Danh sách kề ở trên, các đỉnh được lưu trữ trong Mảng. Mỗi đỉnh có một con trỏ tới Danh sách liên kết với các cạnh được lưu dưới dạng i,w , trong đó i là chỉ mục của đỉnh mà cạnh đi tới và w là trọng số của cạnh đó.
Ví dụ: Nút D có một con trỏ tới Danh sách liên kết có cạnh tới đỉnh A. Các giá trị 0,4 có nghĩa là đỉnh D có cạnh tới đỉnh trên chỉ số 0 (đỉnh A) và trọng số của cạnh đó là 4 .
