Đồ thị là cấu trúc dữ liệu phi tuyến tính. Nó biểu diễn dữ liệu bằng các nút (nodes) và mối quan hệ bằng các cạnh (edges). Một đồ thị G có hai phần: tập đỉnh V và tập cạnh E. Ký hiệu G(V,E).
Trong đồ thị này có 5 đỉnh và 5 cạnh. Các cạnh có hướng. Ví dụ cạnh nối B và D: đỉnh nguồn B, đỉnh đích D. Có thể đi B→D nhưng không đi D→B.
Đồ thị phi tuyến tính, không có cấu trúc quy chuẩn. Để biểu diễn đồ thị trong bộ nhớ, có vài cách:
- Ma trận kề (Adjacency matrix)
- Danh sách cạnh (Edge list)
- Danh sách kề (Adjacency List)
Ở đây chúng ta xem biểu diễn danh sách kề:
Biểu diễn Danh sách kề (Adjacency List Representation)
Biểu diễn này dựa trên Danh sách liên kết (Linked Lists). Mỗi nút giữ một danh sách các nút trực tiếp kết nối với đỉnh đó. Cuối danh sách, mỗi nút nối với giá trị null để báo hiệu kết thúc danh sách.
