Biểu đồ là một cấu trúc dữ liệu phi tuyến tính. Điều này đại diện cho dữ liệu bằng cách sử dụng các nút và quan hệ của chúng bằng cách sử dụng các cạnh. Một đồ thị G có hai phần. Các đỉnh và các cạnh. Các đỉnh được biểu diễn bằng cách sử dụng tập V, và các cạnh được biểu diễn dưới dạng tập E. Vì vậy, ký hiệu đồ thị là G (V, E). Hãy để chúng tôi xem một ví dụ để có được ý tưởng.
Trong đồ thị này, có năm đỉnh và năm cạnh. Các cạnh được định hướng. Ví dụ, nếu chúng ta chọn cạnh nối đỉnh B và D, đỉnh nguồn là B và điểm đến là D. Vì vậy, chúng ta có thể di chuyển B đến D nhưng không di chuyển từ D sang B.
Các đồ thị là phi tuyến tính và nó không có cấu trúc đều đặn. Để biểu diễn một biểu đồ trong bộ nhớ, có một số kiểu khác nhau. Những phong cách này -
- Biểu diễn ma trận kề
- Biểu diễn danh sách cạnh
- Trình bày Danh sách gần kề
Biểu diễn ma trận gần kề
Chúng ta có thể biểu diễn một đồ thị bằng ma trận kề. Ma trận đã cho là ma trận kề. Nó là một ma trận vuông, nhị phân và từ hàng thứ i đến cột thứ j, nếu có cạnh, vị trí đó được đánh dấu là 1. Khi chúng ta cố gắng biểu diễn một đồ thị vô hướng bằng ma trận kề, ma trận sẽ là đối xứng.
Biểu diễn danh sách cạnh
Đồ thị cũng có thể được biểu diễn bằng cách sử dụng mảng một chiều. Đây được gọi là danh sách cạnh. Trong biểu diễn này có năm cạnh hiện diện, đối với mỗi cạnh, phần tử đầu tiên là nguồn và phần tử thứ hai là đích. Đối với biểu diễn đồ thị vô hướng, số phần tử trong danh sách cạnh sẽ được nhân đôi.
Trình bày danh sách gần kề
Đây là một dạng biểu diễn đồ thị khác. Nó được gọi là danh sách kề. Trình bày này dựa trên Danh sách được Liên kết. Trong cách tiếp cận này, mỗi Node đang nắm giữ một danh sách các Node, được kết nối trực tiếp với các đỉnh đó. Ở cuối danh sách, mỗi nút được kết nối với các giá trị null để cho biết rằng đó là nút cuối của danh sách đó.
