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:= Ø;

2
5
7
8
6
10 119