Đồ thị

Đồ thị $G=(V,E)$ gồm tập đỉnh V và tập cạnh E nối các đỉnh. Đồ thị có hướng phân biệt $u\to v$ với $v\to u$. Đồ thị vô hướng thì không. Trọng số là số gắn trên cạnh, thường biểu diễn khoảng cách hoặc chi phí. Đường đi là chuỗi cạnh liên tiếp.

Lĩnh vực: Giải thuật & cấu trúc dữ liệu

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Bài giảng dùng khái niệm này

• Tìm kiếm mù: BFS, DFS, UCS & IDSTri thức & Tìm kiếm
• Tìm kiếm kinh nghiệm: Greedy & A*Tri thức & Tìm kiếm
• Mạng Bayes & suy luậnTri thức & Tìm kiếm
• Quy hoạch tuyến tính và quy hoạch độngToán cho AI
• PageRank: Mô hình & tính toánGiải thuật dữ liệu
• Đồ thị & thuật toán duyệtCTDL & Giải thuật
• Lý thuyết đồ thị cơ bảnToán rời rạc

Giải thích kỹ thuật

Biểu diễn đồ thị. Danh sách kề lưu láng giềng của từng đỉnh và thường cần $O(|V|+|E|)$ bộ nhớ. kề dùng bảng |$V|\times |V|$, thuận tiện kiểm tra cạnh nhưng cần $O(|V{|}^2)$ bộ nhớ.

BFS và DFS duyệt danh sách kề trong $O(|V|+|E|)$ nếu mỗi đỉnh chỉ được xử lý một lần. Một đường đi ngắn nhất theo số cạnh có thể khác đường có tổng trọng số nhỏ nhất.

Ví dụ

$V=\{A,B,C\}$, cạnh $A\to B$ giá 2 và $B\to C$ giá 3: Đường $A\to B\to C$ có tổng chi phí 5.

Khi nào cần dùng?

Mô hình hóa không gian tìm kiếm, mạng liên kết và bài toán đường đi.

Câu hỏi ôn lại

Hai đường có cùng số cạnh có nhất thiết cùng chi phí không?

Xem đáp án

Không. Trọng số các cạnh có thể khác nhau.

Thuật ngữ liên quan

• Cây
• Trạng thái
• Hàng đợi
• Ngăn xếp