BFS Tìm Kiếm Theo Chiều Rộng - Tài Liệu Text - 123doc

Tải bản đầy đủ (.pptx) (35 trang)

1. Trang chủ
>>
2. Giáo án - Bài giảng
>>
3. Tin học

BFS Tìm kiếm theo chiều rộng

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (978.92 KB, 35 trang )

Chủ Đề:Thuật toán BFS và ứng dụngNhóm 1:Bạch Ngọc HiệpNguyễn Duy LongPhạm Quang Hưng Mục lục:•Thuật toán BFS (Breadth First Search) Ý tưởng Các bước thực hiện – giải mã Ví dụ Đánh giá phương pháp.•Ứng dụng thuật toán BFS vào 1 số bài toán.•Tìm đường đi giữa hai đỉnh bất kỳ của đồ thị•Kiểm tra tính chất liên thông của đồ thị•Tìm cây khung của đồ thị•Tài liệu tham khảo•Chương trình mô phỏng các thuật toánBFS (Breadth First Search)Ý tưởng:Cho 1 đỉnh bắt đầu duyệt (A), lập lịch duyệt các đỉnh kề với A. Cứ như vậy duyệt lần lượt theo thứ tự từ gần đến xa.Sử dụng cấu trúc Queue để nạp các đỉnh cần duyệt.BFSThực hiện giải thuậtĐể ghi nhận trạng thái duyệt các đỉnh của đồ thị, ta sử dụng mảng chuaxet[] gồm n phần tử(tương ứng với n đỉnh) để xác định phần tử đã được duyệt.Nếu đỉnh i đã duyệt, chuaxet[i]=0; ngược lại nếu i chưa xét chuaxet[i]=1;Sử dụng cấu trúc hàng đợi Queue để nạp các đỉnh sẽ được duyệt.Thuật toán dừng lại khi hàng đợi rỗng.BFSBFSVí dụ minh họa:IGBĐang xétSắp được xétCAEChưa xétĐã xétDKFVí dụ minh họa:IGBĐang xétSắp được xétCAEChưa xétĐã xétDKFQueueVí dụ minh họa:IGBĐang xétSắp được xétCAEChưa xétĐã xétDKFQueueBCDVí dụ minh họa:IGBĐang xétSắp được xétCAEChưa xétĐã xétDKFQueueCDIGVí dụ minh họa:IGBĐang xétSắp được xétCAEChưa xétĐã xétDKFQueueDIGEFVí dụ minh họa:IGBĐang xétSắp được xétCAEChưa xétĐã xétDKFQueueIGEFVí dụ minh họa:IGBĐang xétSắp được xétCAEChưa xétĐã xétDKFQueueGEFVí dụ minh họa:IGBĐang xétSắp được xétCAEChưa xétĐã xétDKFQueueEFVí dụ minh họa:IGBĐang xétSắp được xétCAEChưa xétĐã xétDKFQueueFKVí dụ minh họa:IGBĐang xétSắp được xétCAEChưa xétĐã xétDKFQueueKBFS- Đánh giá phương pháp:+ Ma trận kề:Đơn giản, trực quan, dễ cài đặt. Để kiểm tra hai đỉnh có kề nhau hay không chỉ cần xem vị trí đó là 0 hay 1.Lãng phí bộ nhớ do dùng ma trận n*n. Khi xét 1 đỉnh bất kỳ thì cần kiểm tra nó với tất cả các đỉnh còn lại, nếu là đỉnh cô lập sẽ tốn thời gian.+ Danh sách cạnh:Nếu đồ thị thưa, sẽ tiết kiệm không gian lưu trữ. Khi cần xét tất cả các cạnh của đồ thị, thời gian thực hiện sẽ nhanh hơn ma trận kề.Khi cần xét tất cả các đỉnh kề với một đỉnh bất kỳ, ta phải xét tất cả các cạnh, lọc ra cạnh cần xét. Dẫn đến việc tốn thời gian khi đồ thị có nhiều cạnh.+ Danh sách kề:Duyệt đồ thị nhanh chóng hơn 2 cách trên.Yếu hơn ma trận kề trong việc xét 2 cạnh có nối với nhau hay không. Vì phải duyệt toàn bộ danh sách kề của một đỉnh.Ứng dụng thuật toán BFSKiểm tra tính chất liên thông của đồ thịTìm đường đi giữa hai đỉnh bất kỳ của đồ thị,Tìm cây khung của đồ thị.Kiểm tra tính liên thông của đồ thịĐịnh nghĩa:G gọi là liên thông (connected) nếu luôn tồn tại đường đi giữa mọi cặp đỉnh phân biệtcủa đồ thị.Nếu G không liên thông thì chắc chắn nó sẽ là hợp của hai hay nhiều đồ thị con liênthông, các đồ thị con này đôi một không có đỉnh chung. Các đồ thị con liên thông rờinhau như vậy được gọi là thành phần liên thông của đô thị đang xét.Kiểm tra tính liên thông của đồ thịVD:Đồ thị liên thôngKiểm tra tính liên thông của đồ thịĐồ thị không liên thôngKiểm tra tính liên thông của đồ thịÝ tưởng:Nếu đồ thị liên thông thì số thành phần liên thông của nó là 1. Điều này tương đương với phép duyệt theo thủ tụcBFS() được gọi đến đúng 1 lầnSau 1 lần duyệt BFS() nếu còn đỉnh nào chưa xét tức là đồ thị không liên thôngKiểm tra tính liên thông của đồ thịPhương pháp:Để xác định tính liên thông của đồ thị. Ta sử dụng lại mảng chuaxet[] từ thuật toán BFS();Nếu 1 phần tử trong mảng chuaxet[] có giá trị 1 tức là có đỉnh chưa được xét thì đồ thị không liên thông,Ngược lại nếu tất cả các đỉnh đã được đánh dấu đã xét thì đồ thị liên thông.Kiểm tra tính liên thông của đồ thịGiải mã:void Connected(int V)BFS(V);//Gọi thuật toán duyệt BFSfor(int i=0;i