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. ợ ể ư ử ụ ẽ ượ ộ ỉ ệ ươ ư ự ệ ậ ớ ươ ề ộ ệ c đ a vào trong hàng đ i,thì ta b sung c nh (u,v) vào t p F. - Khi đ nh v nào đ ỉ ượ ư ạ ậ ợ ổ 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. ở ạ ậ ắ ầ ư ỉ ặ ợ ỗ - 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. Sau khi l y đ nh 1 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 2 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 đ nh 3 t ỉ ấ ừ ư ế ẫ ạ ợ ợ ỉ ượ ư ậ - L y 4 t hàng đ i, đ nh {8} đ c đ a vào t p F. ấ ừ ợ ỉ ượ ư c đ a vào hàng đ i, và c nh (4,8) đ ợ ạ ượ ư ậ - L y 5 t hàng đ i, đ nh {9} đ c đ a vào t p F. ấ ừ ợ ỉ ượ ư c đ a vào hàng đ i, và c nh (5,9) đ ợ ạ ượ ư ậ - L y 6 t c đ a vào hàng đ i, các c nh (6,10) và (6,11) đ c đ a vào t p F. ấ ừ hàng đ i, đ nh {10,11} đ ỉ ợ ượ ư ạ ợ ượ ư ậ - 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 đ thu t toán BFS bao g m các c nh sau: ủ ồ ị ư ậ c t ượ ừ ậ ạ ồ F = { (1,2), (1,3), (2,4), (2,5), (3,6), (3,7), (4,8), (5,9), (6,10), (6,11) }
Quá trình th đ c mô t theo hình v sau: duy t ệ đ ồ ị ượ ả ẽ
1
2 3
4 5 6 7
8 9 10 11
