Sự khác biệt giữa đồ thị và cây

Đồ thị vs cây

Đồ thị và cây được sử dụng trong các cấu trúc dữ liệu. Chắc chắn có một số khác biệt giữa Đồ thị và Cây. Một tập hợp các đỉnh có quan hệ nhị phân được gọi là biểu đồ trong khi cây là cấu trúc dữ liệu có một tập hợp các nút được liên kết với nhau.

Đồ thị

Biểu đồ là một tập hợp các mục được kết nối bởi các cạnh và mỗi mục được gọi là nút hoặc đỉnh. Nói cách khác, một biểu đồ có thể được định nghĩa là tập hợp các đỉnh và có mối quan hệ nhị phân giữa các đỉnh này.

Khi thực hiện một biểu đồ, các nút được thực hiện dưới dạng các đối tượng hoặc cấu trúc. Các cạnh có thể được đại diện theo những cách khác nhau. Một trong những cách là mỗi nút có thể được liên kết với một mảng cạnh sự cố. Nếu thông tin sẽ được lưu trữ trong các nút chứ không phải các cạnh thì các mảng đóng vai trò là con trỏ tới các nút và cũng đại diện cho các cạnh. Một trong những lợi thế của phương pháp này là các nút bổ sung có thể được thêm vào biểu đồ. Các nút hiện có có thể được kết nối bằng cách thêm các phần tử vào mảng. Nhưng có một nhược điểm vì cần có thời gian để xác định xem có một cạnh giữa các nút không.

Một cách khác để làm điều này là giữ một mảng hai chiều hoặc ma trận M có các giá trị Boolean. Sự tồn tại của cạnh từ nút i đến j được chỉ định bởi mục nhập Mij. Một trong những lợi thế của phương pháp này là tìm hiểu xem có bất kỳ cạnh nào giữa hai nút không.

Cây

Cây cũng là một cấu trúc dữ liệu được sử dụng trong khoa học máy tính. Nó tương tự như cấu trúc của cây và có một tập hợp các nút được liên kết với nhau.

Một nút của cây có thể chứa một điều kiện hoặc giá trị. Nó cũng có thể là một cây của riêng nó hoặc nó có thể đại diện cho một cấu trúc dữ liệu riêng biệt. Không có hoặc nhiều nút có mặt trong cấu trúc dữ liệu cây. Nếu một nút có một con thì nó được gọi là nút cha của con đó. Có thể có nhiều nhất một cha mẹ của một nút. Đường dẫn xuống dài nhất từ ​​nút đến lá là chiều cao của nút. Độ sâu của nút được biểu thị bằng đường dẫn đến gốc của nó.

Trong một cây, nút trên cùng được gọi là nút gốc. Nút gốc không có cha mẹ vì nó là nút nhiều nhất. Từ nút này, tất cả các hoạt động cây bắt đầu. Bằng cách sử dụng các liên kết hoặc các cạnh, các nút khác có thể đạt được từ nút gốc. Các nút cấp thấp nhất được gọi là nút lá và họ không có con. Nút có số lượng nút con được gọi là nút bên trong hoặc nút bên trong.