Chương 7: Đồ thị
Khái niệm về đồ thị
Biểu diễn đồ thị
Bài toán tìm đường đi trên đồ thị
Đa đồ thị
Các khái niệm
Định nghĩa
Đồ thị G = (V,E)
V: tập hợp hữu hạn các phần tử (đỉnh hay nút)
E: tập hữu hạn các cạnh (cung)
17 trang |
Chia sẻ: phuongt97 | Lượt xem: 499 | Lượt tải: 0
Nội dung tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 7: Đồ thị - Ngô Quang Thạch, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
CẤU TRÚC DỮ LIỆU VÀ
GIẢI THUẬT
NGÔ QUANG THẠCH
Email: thachnq@gmail.com
ĐT: 01273984123
Chương 7: Đồ thị
Khái niệm về đồ thị
Biểu diễn đồ thị
Bài toán tìm đường đi trên đồ thị
Sơ đồ giao thông
Đơn đồ thị
Đa đồ thị
Các khái niệm
Các khái niệm
Định nghĩa
Đồ thị G = (V,E)
. V: tập hợp hữu hạn các phần tử (đỉnh hay nút)
. E: tập hữu hạn các cạnh (cung)
.
Các khái niệm
Đồ thị có trọng số
Biểu diễn đồ thị
Biểu diễn đồ thị bằng ma trận kề
Các khái niệm mở đầu
Bài toán: Cho G = là đồ thị có trọng số. s và t là 2
đỉnh của đồ thị. Hãy tìm đường đi có tổng trọng số nhỏ
nhất từ s đến t.
VD: Tìm đường đi ngắn nhất từ đỉnh 3 đến đỉnh 5
1 10 2
5
7 20
3 1
9 5
3 4 5
12 19-Dec-15
Bài toán đường đi ngắn nhất
Đường đi ngắn nhất từ 1 đến 4 là: 1->2->3->6->5->4
Đường đi ngắn nhất xuất phát từ 1 đỉnh
Nhận xét:
. Nếu v là đỉnh trung gian trên đường đi ngắn nhất từ s đến t thì
đường đi từ s đến v phải là ngắn nhất và đường đi từ v đến t
cũng phải là ngắn nhất.
s v t
X
. Do đó, để tối ưu, người ta mở rộng bài toán tìm đường đi
ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại của đồ thị.
14 19-Dec-15
Đường đi ngắn nhất xuất phát từ 1 đỉnh (tt)
Ý tưởng chung của các thuật toán tìm đường đi ngắn nhất.
. Dò tìm bằng cách thử đi qua các đỉnh trung gian
. Nếu phát hiện đường đi qua đỉnh trung gian ngắn hơn đường đi
hiện tại thì sẽ cập nhật đường đi mới, đồng thời chỉnh sửa các
thông tin liên quan.
. Sử dụng hai mảng để lưu trữ tạm thời:
• Mảng d[v]: Lưu trữ độ dài đường đi ngắn nhất hiện tại từ s đến v.
• Mảng T[v]: Lưu trữ đỉnh nằm trước v trên đường đi ngắn nhất hiện tại.
15 19-Dec-15
Đường đi ngắn nhất xuất phát từ 1 đỉnh (tt)
Ý tưởng chung của các thuật toán tìm đường đi ngắn nhất
(tt):
Truoc[v]
d[v]
s X v
c[u,v]
d[u] u
if d[v] > d[u] + c[u,v] then
{ d[v] = d[u] + c[u,v];
Truoc[v] = u; }
16 19-Dec-15
Tự tham khảo các thuật toán tìm đường đi ngắn nhất
Các file đính kèm theo tài liệu này:
- bai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_7_do_thi_ngo.pdf