Sự khác nhau giữa Graph và Tree

Đồ thị và Cây

Đồ thị và Cây được sử dụng trong cấu trúc dữ liệu. Chắc chắn có một số sự khác biệt giữa đồ thị và cây. Một tập các đỉnh có quan hệ nhị phân được gọi là đồ thị trong khi cây là một cấu trúc dữ liệu có một tậ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, đồ thị có thể được định nghĩa là tập các đỉnh và có một mối quan hệ nhị phân giữa các đỉnh này.

Trong việc thực hiện một đồ thị, các nút được thực hiện như các đối tượng hoặc cấu trúc. Các cạnh có thể được biểu 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 được lưu trữ trong các nút thay vì cạnh thì mảng hoạt động như các con trỏ tới các nút và cũng là các cạnh. Một trong những ưu điểm của cách tiếp cận này là các nút bổ sung có thể được thêm vào biểu đồ. Các nút hiện tại có thể được kết nối bằng cách thêm các phần tử vào các mảng. Nhưng có một bất lợi vì thời gian là cần thiết để xác định xem có một cạnh giữa các nú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ó giá trị Boolean. Sự tồn tại của cạnh từ nút i đến j được xác định bằng cách nhập Mij. Một trong những lợi thế của phương pháp này là để tìm ra nếu có bất kỳ cạnh giữa hai nút.

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 riêng của nó hoặc nó có thể đại diện cho một cấu trúc dữ liệu riêng biệt. Zero 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ó con thì nó được gọi là nút cha của đứa trẻ đó. Có thể có tối đa một bậc cha mẹ của một nút. Đường đi xuống dài nhất từ ​​nút tới lá là chiều cao của nút. Độ sâu của nút được thể hiện bằng đường dẫn tới 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à đầu nhiều nhất. Từ nút này, tất cả hoạt động của cây bắt đầu. Bằng cách sử dụng liên kết hoặc cạnh, các nút khác có thể đạt được từ nút gốc. Các nút dưới cùng mức cao nhất được gọi là các nút lá và họ không có con. Nút có số 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 đồ thị và cây: • Một cây có thể được mô tả như là một trường hợp chuyên biệt của đồ thị không có vòng và vòng. • Không có vòng trong cây, trong khi đồ thị có thể có vòng lặp. • Có ba bộ trong một biểu đồ i. e. cạnh, đỉnh và một tập đại diện cho 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. • Trên cây có rất nhiều quy tắc đánh vần cách kết nối các nút có thể xảy ra trong khi đồ thị không có quy tắc dictating kết nối giữa các nút.