Đồ thị so với Cây
Graph và Tree được sử dụng trong 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. Tập hợp các đỉnh có quan hệ nhị phân được gọi là đồ thị trong khi cây là cấu trúc dữ liệu có tập hợp các nút được liên kết với nhau.
Đồ thị
Đồ thị là một tập hợp các mục được nối với nhau bằng 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 đồ thị 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 đồ thị, 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 biểu diễn theo nhiều 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 đượ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ỏ đến các nút và cũng đại diện cho các cạnh. Một trong những ưu điểm của phương pháp này là có thể thêm các nút bổ sung 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 là vì cần phải có thời gian để xác định liệu có cạnh giữa các nút hay không.
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 nút j được chỉ định bởi mục Mij. Một trong những ưu điểm của phương pháp này là tìm xem có cạnh nào giữa hai nút hay 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 hoặc nhiều nút có trong cấu trúc dữ liệu dạng cây. Nếu một nút có một nút con thì nó được gọi là nút cha của nút con đó. Có thể có nhiều nhất một nút cha. Đường đi 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 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 trên cùng. Từ nút này, tất cả các hoạt động của 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ể được tiếp cận từ nút gốc. Các nút cấp dưới cùng được gọi là nút lá và chúng không có bất kỳ nút con nào. 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.
Sự khác biệt giữa biểu đồ và cây:
• Một cây có thể được mô tả như một trường hợp đặc biệt của đồ thị không có vòng lặp và mạch tự.
• Không có vòng lặp nào trong một cây trong khi biểu đồ có thể có các vòng lặp.
• Có ba tập hợp trong một đồ thị, tức là các cạnh, đỉnh và một tập hợp biểu thị mối quan hệ của chúng trong khi một cây bao gồm các nút được kết nối với nhau. Các kết nối này được gọi là các cạnh.
• Trong cây có rất nhiều quy tắc đánh vần cách kết nối của các nút có thể xảy ra trong khi biểu đồ không có quy tắc nào chỉ ra kết nối giữa các nút.
