Đồ Thị Khi các cấu trúc dữ liệu thuật toán - núm vú

Đồ thị là một dạng của cấu trúc dữ liệu chung được sử dụng trong các thuật toán. Bạn thấy đồ thị được sử dụng ở những nơi như bản đồ cho GPS và tất cả các loại nơi khác mà cách tiếp cận trên cùng của cấu trúc cây sẽ không hoạt động.

Biểu đồ là một loại của một phần mở rộng cây. Giống như cây, bạn có các nút kết nối với nhau để tạo ra các mối quan hệ. Tuy nhiên, không giống như cây nhị phân, đồ thị có thể có nhiều hơn một hoặc hai kết nối. Trên thực tế, các nút biểu đồ thường có rất nhiều kết nối. Tuy nhiên, để giữ mọi thứ đơn giản, hãy xem biểu đồ được hiển thị.

Các nút đồ thị có thể kết nối với nhau bằng vô số cách.

Trong trường hợp này, đồ thị tạo ra một vành đai A kết nối với cả B và F. Tuy nhiên, nó không phải là như vậy. A có thể là một nút bị ngắt kết nối hoặc cũng có thể kết nối với C. Một đồ thị cho thấy sự kết nối giữa các nút theo cách hữu ích cho việc xác định các mối quan hệ phức tạp.

Các đồ thị cũng thêm một vài bước xoắn mới mà bạn có thể chưa từng nghĩ đến trước đây. Ví dụ, một biểu đồ có thể bao gồm các khái niệm directionality. Không giống như cây, có mối quan hệ cha / con, nút đồ thị có thể kết nối với bất kỳ nút nào khác với một hướng cụ thể trong tâm trí. Hãy suy nghĩ về đường phố trong thành phố. Hầu hết các đường phố là đường hai chiều, nhưng một số đường một chiều cho phép di chuyển theo một hướng.

Việc trình bày kết nối đồ thị có thể không phản ánh thực tế của biểu đồ. Biểu đồ có thể chỉ định trọng lượng cho một kết nối cụ thể. Trọng lượng có thể xác định khoảng cách giữa hai điểm, xác định thời gian cần thiết để đi qua tuyến đường hoặc cung cấp các loại thông tin khác.