TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị: Chương 3 - Các thuật toán tìm kiếm trên đồ thị

Bài giảng Lý thuyết đồ thị: Chương 3 - Các thuật toán tìm kiếm trên đồ thị trình bày về tìm kiếm theo chiều sâu (Depth First Search – DFS); tìm kiếm theo chiều rộng (Breadth First Search - BFS); ứng dụng các thuật toán tìm kiếm trên đồ thị. Mời các bạn tham khảo. | Chương 3 CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ Phần TÌM KIẾM THEO CHIỀU SÂU (Depth First Search – DFS) Ý tưởng 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 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 5/14/2020 4:49:36 AM Lý thuyết đồ thị 1 2 3 4 5 6 Cài đặt DFS 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 5/14/2020 4:49:36 AM Lý thuyết đồ thị Cài đặt DFS (tt) 5/14/2020 4:49:36 AM Lý thuyết đồ thị void DFS(DOTHI g, int s) // s la dinh xuat phat { int danhdau[maxV]; Stack st; //Khoi tao for (int i = 1; i=1; i--) if (!danhdau[i] && [v][i] != 0) Push(st,v); } } } Cài đặt DFS (tt) Đư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, 3 vào Stack Lấy 5 ra xử lý, đưa 4 vào Stack Lấy 4 ra xử lý. Không đưa gì vào Stack Lấy 6 ra xử lý. Không đưa gì vào Stack Lấy 5 ra. Không xử lý (vì đã xử lý rồi) Lấy 4 ra. Không xử lý Lấy 5 ra. Không xử lý 5/14/2020 4:49:36 AM Lý thuyết đồ thị 1 2 3 4 5 6 1 1 5 4 2 5 3 2 3 6 5 5 4 4 6 Stack Thứ tự duyệt: Ví dụ về DFS Áp dụng DFS, hãy thể hiện thứ tự duyệt các đỉnh trong đồ thị sau: 5/14/2020 4:49:36 AM Lý thuyết đồ thị Đáp án: 0 1 2 3 4 9 5 6 7 8 10 u v t s x Đáp án: t u s v Đỉnh x không được duyệt 0 Phần TÌM KIẾM THEO CHIỀU RỘNG (Breadth .

• Toán học
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Thuật toán tìm kiếm trên đồ 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
• Ứng dụng thuật toán tìm kiếm đồ thị
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị