Graph - Đồ thị

Repo này nói về đồ thị

Đồ thị là gì?

Đồ thị là một cấu trúc dữ liệu (CTDL) bao gồm các đỉnh và cạnh được nối với nhau. Đồ thị mô tả các đối tượng và các mối quan hệ giữa chúng. Các đối tượng được gọi là đỉnh (hay nút, điểm), còn mối quan hệ giữa các đối tượng gọi là cạnh (hay liên kết, đường thẳng).

Thông thường, đồ thị được mô tả dưới dạng sơ đồ với các chấm hoặc hình tròn đại diện cho đỉnh và các đường thẳng hoặc đường cong đại diện cho các cạnh.

Wikipedia

---

1. Đồ thị có hướng (Directed Graph hay Digraph)

Đồ thị có hướng bao gồm các đỉnh và cạnh được nối với nhau, nhưng các cạnh có hướng (thể hiện bằng mũi tên) chỉ ra chiều đi của các kết nối.

• Ví dụ: Nếu có cạnh từ A -> B, chỉ có một con đường duy nhất từ A đến B. Không thể đi ngược lại từ B -> A.

Source image: Wikipedia

---

2. Đồ thị vô hướng (Undirected Graph)

Đồ thị vô hướng là đồ thị mà các cạnh không có hướng, nghĩa là nếu có một cạnh nối giữa hai đỉnh A và B, bạn có thể di chuyển từ A đến B hoặc từ B đến A mà không phân biệt chiều của cạnh.

• Ví dụ: Nếu có cạnh từ A -> B, thì có thể đi ngược lại từ B -> A

3. Trọng số (Weight)

Trọng số là giá trị gán cho mỗi cạnh có đồ thị,tùy theo tính chất bài toán mà có các ý ngĩa khác nhau ví dụ: Khoảng cách,chi phí,...

Ma trận kề,Danh sách kề,Danh sách cạnh

Danh sách cạnh

• Cho một đồ thị như sau:

• Thì đồ thị sẽ có sanh sách cạnh là:

1 2
1 4
2 3
4 5
5 3