Đồ thị là cấu trúc dữ liệu phi tuyến tính. Biểu diễn dữ liệu bằng nút, và quan hệ bằng cạnh. Đồ thị G có hai phần: đỉnh (Vertices) và cạnh (Edges). Đỉnh dùng tập V, cạnh dùng tập E. Ký hiệu đồ thị G(V,E). Ví dụ:
Đồ thị này có 5 đỉnh và 5 cạnh. Cạnh có hướng. Ví dụ cạnh nối B và D, nguồn là B đích là D. Có thể đi B→D nhưng không D→B.
Đồ thị phi tuyến tính, không cấu trúc नियम. Để biểu diễn trong bộ nhớ, có vài cách:
- Biểu diễn ma trận kề (Adjacency matrix)
- Biểu diễn danh sách cạnh (Edge list)
- Biểu diễn danh sách kề (Adjacency List)
Biểu diễn Ma trận kề
Dùng ma trận kề biểu diễn đồ thị. Ma trận nhị phân vuông, từ hàng i đến cột j, nếu có cạnh thì đánh dấu 1. Nếu đồ thị vô hướng, ma trận đối xứng.
Biểu diễn Danh sách cạnh
Đồ thị có thể biểu diễn bằng mảng 1 chiều gọi là danh sách cạnh. Mỗi cạnh: phần tử đầu là nguồn, thứ hai là đích. Đồ thị vô hướng thì số phần tử gấp đôi.
Biểu diễn Danh sách kề
Cách biểu diễn khác dựa trên Danh sách liên kết. Mỗi nút giữ danh sách các nút kết nối trực tiếp. Cuối danh sách nối với null để báo hiệu kết thúc.
