NỘI DUNG
1. Đồ thị
Đồ thị vô hướng, Đồ thị có hướng,Tính liên thông của đồ thị
2. Biểu diễn đồ thị
Biểu diễn đồ thị bởi ma trận, Danh sách kề, Danh sách cạnh
3. Các thuật toán duyệt đồ thị
Thuật toán tìm kiếm theo chiều sâu, Thuật toán tìm kiếm theo chiều rộng
4. Một số ứng dụng của tìm kiếm trên đồ thị
Bài toán đường đi, Bài toán liên thông,
Đồ thị không chứa chu trình và bài toán sắp xếp tôpô, Bài toán tô màu đỉnh đồ thị
5. Bài toán cây khung nhỏ nhất
Thuật toán Kruscal, Cấu trúc dữ liệu biểu diễn phân hoạch,
6. Bài toán đường đi ngắn nhất
Thuật toán Dijkstra, Cài đặt thuật toán với các cấu trúc dữ liệu
Nguyễn Đức Nghĩa -Bộ môn KHMT ĐHBKHN 2
CuuDuongThanCong.com
3
1. Đồ thị
Đồ thị là cặp (V, E), trong đó
Vlà tập đỉnh
Elà họ các cặp đỉnh gọi là các cạnh
Ví dụ:
Các đỉnh là các sân bay
Các cạnh thể hiện đường bay nối hai sân bay
Các số trên cạnh có thể là chi phí (thời gian, khoảng cách)
DAN DBP
VIN
NHT
HAP
BKK
HCM
HAN
Nguyễn Đức Nghĩa -Bộ môn KHMT ĐHBKHN
CuuDuongThanCong.com
4
Các kiểu cạnh
Cạnh có hướng (Directed edge)
Cặp có thứ tự gồm hai đỉnh (u,v)
Đỉnh ulà đỉnh đầu
Đỉnh vlà đỉnh cuối
Ví dụ, chuyến bay
Cạnh vô hướng (Undirected edge)
Cặp không có thứ tự gồm 2 đỉnh (u,v)
Ví dụ, tuyến bay
Đồ thị có hướng (digraph)
Các cạnh có hướng
Ví dụ, mạng truyền tin
Đồ thị vô hướng (Undirected graph/graph)
Các cạnh không có hướng
Ví dụ, mạng tuyến bay
HAN HCM
flight
VN 426
HAN HCM
1135
km
Nguyễn Đức Nghĩa -Bộ môn KHMT ĐHBKHN
CuuDuongThanCong.com
5
Ứng dụng
Mạch lôgic (Electronic circuits)
Mạch in
Mạch tích hợp
Mạng giao thông (Transportation
networks)
Mạng xa lộ
Mạng tuyến bay
Mạng máy tính (Computer
networks)
Mạng cục bộ
Internet
Web
Cơ sở dữ liệu (Databases)
Sơ đồ quan hệ thực thể
(Entity-relationship diagram) Bờm
Chị Hằng
Cuội
Trường ĐHQG
Tổ Tin
Phòng Giáo vụ
Phòng Tuyên huấn
Ban Giám đốc
Phòng hành chính
Phòng máy 2Phòng máy 1
Nguyễn Đức Nghĩa -Bộ môn KHMT ĐHBKHN
CuuDuongThanCong.com
