Như chúng ta biết rằng các biểu đồ có thể được phân loại thành các biến thể khác nhau. Chúng có thể được định hướng hoặc vô hướng, và chúng có thể có trọng số hoặc không có trọng số. Ở đây chúng ta sẽ xem cách biểu diễn đồ thị có trọng số trong bộ nhớ. Hãy xem xét biểu đồ sau -
Biểu diễn ma trận kề
Để lưu trữ đồ thị có trọng số bằng cách sử dụng dạng ma trận kề, chúng ta gọi ma trận là ma trận chi phí. Ở đây mỗi ô tại vị trí M [i, j] đang giữ trọng số từ cạnh i đến j. Nếu không có cạnh, thì nó sẽ là vô cùng. Đối với cùng một nút, nó sẽ là 0.
| 0 | ∞ | 6 | 3 | ∞ |
| 3 | 0 | ∞ | ∞ | ∞ |
| ∞ | ∞ | 0 | 2 | ∞ |
| ∞ | 1 | 1 | 0 | ∞ |
| ∞ | 4 | ∞ | 2 | 0 |
Biểu diễn Danh sách gần kề
Trong danh sách kề, mỗi phần tử trong danh sách sẽ có hai giá trị. Nút đầu tiên là nút đích và nút thứ hai là trọng số giữa hai nút này. Biểu diễn như dưới đây.
