Thiết kế và cài đặt thuật toán xây dựng cây khung theo chiều rộng BFS

Chia sẻ: Chao Hello | Ngày: | Loại File: DOC | Số trang:3

Thêm vào BST

Báo xấu

392
lượt xem 58
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tư tưởng của thuật toán: Xuất phát từ đỉnh u, và khởi tạo tập các cạnh của cây khung F là rỗng. Sử dụng một hàng đợi để lưu các đỉnh sẽ được duyệt trong tương lai.Thực hiện các thuật toán như làm với phương pháp duyệt theo chiều rộng. Khi đỉnh v nào được đưa vào trong hàng đợi,thì ta bổ sung cạnh (u,v) vào tập F.

Chủ đề:

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

Lưu

Nội dung Text: Thiết kế và cài đặt thuật toán xây dựng cây khung theo chiều rộng BFS

Thiết kế và cài đặt thuật toán xây dựng cây khung theo chiều rộng BFS: 1.Thuật toán: 1.1 Tư tưởng của thuật toán: -Xuất phát từ đỉnh u, và khởi tạo tập các cạnh của cây khung F là rỗng. -Sử dụng một hàng đợi để lưu các đỉnh sẽ được duyệt trong tương lai.Thực hiện các thuật toán như làm với phương pháp duyệt theo chiều rộng. - Khi đỉnh v nào được đưa vào trong hàng đợi,thì ta bổ sung cạnh (u,v) vào tập F. Thuật toán được mô tả như sau: Procedure stree_BFS(u); (*tìm kiếm theo chiều rộng áp dụng tìm tập cạnh của cây khung F của đồ thị vô hướng liên thông G cho bởi danh sách kề*) Begin Queue := Ø; Queue ← u; Chuaxet[u]:=false; While Queue ≠ Ø do Begin v← Queue ; For W ke(v) do If chuaxet[v] then Begin Queue ← v; Chuaxet[u]:=false; F:=F U (u,v); End; End; End; (* main program*) ; BEGIN For u thuoc V do Chuaxet[u]:=true; (*F la tap canh cua cay khung *) F:= Ø; (* root la mot dinh tuy y cua do thi*) Stree_BFS(root); END. (độ phức tạp của thuật toán này : O( m +n )) Ví dụ: Cho đồ thị sau: Tìm cây khung của đồ thị sử dụng phương pháp tìm kiếm theo chiều rộng .
1 2 3 4 5 6 7 8 9 10 11 Bài làm : - Đưa đỉnh 1 vào hàng đợi, khởi tạo tập F là rỗng. Bắt đầu quá trình lặp. - Sau khi lấy đỉnh 1 từ hàng đợi, các đỉnh {2,3} đưa vào hàng đợi , dẫn đến các cạnh (1,2) và (1,3) sẽ đưa vào tập F. - Lấy đỉnh 2 từ hàng đợi, các đỉnh {4,5} đưa vào hàng đợi, dẫn đến các cạnh (2,4) và (2,5) được đưa vào tập F. - Lấy đỉnh 3 từ hàng đợi, các đỉnh {6,7} đưa vào hàng đợi, dẫn đến các cạnh (3,6) và (3,7) được đưa vào tập F. - Lấy 4 từ hàng đợi, đỉnh {8} được đưa vào hàng đợi, và cạnh (4,8) được đưa vào tập F. - Lấy 5 từ hàng đợi, đỉnh {9} được đưa vào hàng đợi, và cạnh (5,9) được đưa vào tập F. - Lấy 6 từ hàng đợi, đỉnh {10,11} được đưa vào hàng đợi, các cạnh (6,10) và (6,11) được đưa vào tập F. - Lấy các đỉnh 7, 8, 9, 10, 11 ra từ hàng đợi mà không bổ sung thêm cạnh nào vào tập F. Như vậy cây khung của đồ thị thu được từ thuật toán BFS bao gồm các cạnh sau: F = { (1,2), (1,3), (2,4), (2,5), (3,6), (3,7), (4,8), (5,9), (6,10), (6,11) }
Quá trình duyệt đồ thị được mô tả theo hình vẽ sau: 1 2 3 4 5 6 7 8 9 10 11