intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Lý thuyết đồ thị: Chương 3 - Nguyễn Trần Phi Phượng

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST
Báo xấu
96
lượt xem 5
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết đồ thị: Chương 3 - Các thuật toán tìm kiếm trên đồ thị và ứng dụng của Nguyễn Trần Phi Phương sau đây trình bày về tìm kiếm theo chiều sâu trên đồ thị; tìm kiếm theo chiều rộng trên đồ thị; tìm đường đi và kiểm tra tính liên thông.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 3 - Nguyễn Trần Phi Phượng

  1. Chương 3 CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG
  2. 3.1 Tìm kiếm theo chiều sâu trên đồ thị Depth First Search ƒ B1. Xuất phát từ 1 đỉnh cho trước nào đó. ƒ B2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau. ƒ B3. Đưa tất cả các đỉnh kề với nó vào danh sách xử lý và chọn 1 đỉnh để xử lý tiếp theo. ƒ B4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách. VD: ƒ Bắt đầu từ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5 1 2 3 ƒ Chọn 2 để xử lý. Đưa các đỉnh kề với 2 vào DS: 3, 4, 5, … Thứ tự: 1 2 3 5 4 6 4 5 6 17/03/2011 Lý thuyết đồ thị 2
  3. 3.1 Tìm kiếm theo chiều sâu trên đồ thị Phân tích: – Dùng cấu trúc Stack – Sử dụng mảng đánh dấu là mảng 1 chiều: • int danhdau[maxV]; • Quy ước: – danhdau[i] = 0; đỉnh i chưa được xét – danhdau[i] = 1; đỉnh i đã được xét 17/03/2011 Lý thuyết đồ thị 3
  4. 3.1 Tìm kiếm theo chiều sâu trên đồ thị void DFS(DOTHI g, int s) // s la dinh xuat phat { int danhdau[maxV]; Stack st; //Khoi tao for (int i = 1; i
  5. 3.1 Tìm kiếm theo chiều sâu trên đồ thị 1 2 3 ƒ Đưa 1 vào Stack ƒ Lấy 1 ra xử lý, đưa 5, 4, 2 vào Stack ƒ Lấy 2 ra xử lý, đưa 5, 3 vào Stack ƒ Lấy 3 ra xử lý, đưa 6, 5 vào Stack 6 4 5 ƒ Lấy 5 ra xử lý, đưa 4 vào Stack ƒ Lấy 4 ra xử lý. Không đưa gì vào Stack 5 4 ƒ Lấy 6 ra xử lý. Không đưa gì vào Stack 3 6 5 2 Stack ƒ Lấy 5 ra. Không xử lý (vì đã xử lý rồi) 4 ƒ Lấy 4 ra. Không xử lý 1 5 ƒ Lấy 5 ra. Không xử lý Thứ tự duyệt: 1 2 3 5 4 6 17/03/2011 Lý thuyết đồ thị 5
  6. 3.1 Tìm kiếm theo chiều sâu trên đồ thị ƒÁp dụng DFS, hãy thể hiện thứ tự duyệt các đỉnh trong đồ thị sau: u 0 t v s x Đáp án: 0 1 2 3 4 9 5 6 7 8 10 Đáp án: t u s v Đỉnh x không được duyệt 17/03/2011 Lý thuyết đồ thị 6
  7. 3.2 Tìm kiếm theo chiều rộng trên đồ thị Breadth First Search ƒ B1. Xuất phát từ 1 đỉnh cho trước nào đó. ƒ B2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau. ƒ B3. Đưa tất cả các đỉnh kề với nó vào danh sách xử lý và lần lượt xử lý các đỉnh kề với đỉnh đang xét. ƒ B4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách. VD: ƒ Bắt đầu từ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5 1 2 3 ƒ Chọn 2 để xử lý. Đưa các đỉnh kề với 2 vào DS: 3, 4, 5, … Thứ tự: 1 2 4 5 3 6 4 5 6 17/03/2011 Lý thuyết đồ thị 7
  8. 3.2 Tìm kiếm theo chiều rộng trên đồ thị Phân tích: – Dùng cấu trúc Queue – Sử dụng mảng đánh dấu là mảng 1 chiều: • int danhdau[maxV]; • Quy ước: – danhdau[i] = 0; đỉnh i chưa được xét – danhdau[i] = 1; đỉnh i đã được xét 17/03/2011 Lý thuyết đồ thị 8
  9. 3.2 Tìm kiếm theo chiều rộng trên đồ thị void BFS(DOTHI g, int s) // s la dinh xuat phat { int danhdau[maxV]; Queue q; //Khoi tao for (int i = 1; i
  10. 3.2 Tìm kiếm theo chiều rộng trên đồ thị 1 2 3 ƒ Đưa 1 vào Queue ƒ Lấy 1 ra xử lý, đưa 2, 4, 5 vào Queue ƒ Lấy 2 ra xử lý, đưa 3, 5 vào Queue ƒ Lấy 4 ra xử lý, đưa 5 vào Queue 4 5 6 6 ƒ Lấy 5 ra xử lý, đưa 3 vào Queue 3 ƒ Lấy 3 ra xử lý. Đưa 6 vào Queue 5 ƒ Lấy 5 ra. Không xử lý (vì đã xử lý rồi) 5 Queue ƒ Lấy 5 ra. Không xử lý 3 ƒ Lấy 3 ra. Không xử lý 5 ƒ Lấy 6 ra xử lý. Không đưa gì vào Queue 4 1 2 Thứ tự duyệt: 1 2 4 5 3 6 17/03/2011 Lý thuyết đồ thị 10
  11. 3.2 Tìm kiếm theo chiều rộng trên đồ thị ƒÁp dụng BFS, hãy thể hiện thứ tự duyệt các đỉnh trong đồ thị sau: u 0 t v s x Đáp án: 0 1 3 9 2 4 5 6 8 10 7 Đáp án: t u s v Đỉnh x không được duyệt 17/03/2011 Lý thuyết đồ thị 11
  12. 3.3 Tìm đường đi và kiểm tra tính liên thông Bài toán tìm đường đi giữa hai đỉnh. Giả sử s và t là hai đỉnh nào đó của đồ thị. Hãy tìm đường đi từ s đến t. Thủ tục DFS(s) (BFS(s)) sẽ cho phép thăm tất cả các đỉnh thuộc cùng một thành phần liên thông với s. Vì vậy, sau khi thực hiện xong thủ tục, nếu danhdau[t]=0 thì không có đường đi từ s đến t. 17/03/2011 Lý thuyết đồ thị 12
  13. 3.3 Tìm đường đi và kiểm tra tính liên thông Kiểm tra tính liên thông. – Áp dụng cho đồ thị vô hướng – Áp dụng DFS, bắt đầu từ đỉnh bất kỳ, nếu duyệt qua được tất cả các đỉnh thì đồ thị là liên thông – Cụ thể: • Sử dụng thêm biến dem để đếm số đỉnh được duyệt • Nếu duyệt xong mà đếm bằng g.nV (số đỉnh của đồ thị) thì có nghĩa là tất cả các đỉnh được duyệt 17/03/2011 Lý thuyết đồ thị 13
  14. 3.3 Tìm đường đi và kiểm tra tính liên thông int danhdau[maxV] void DFS_lt(DOTHI g, int s, int &dem) // s la dinh xuat phat { dem++; danhdau[s] = 1; for (int v = 1; v
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
3=>0