BFS (Breadth-First Search) tu dinh nguon A tren do thi vo huong 6 dinh. Duy tri song song: graph G, cay BFS T (ban dau chi co root A, phan con lai "hidden"), queue Q (frontier), va mang visited V voi nhan 0..5 anh xa A..F.
Step 2 / 16
Khoi dau: enqueue A vao Q, danh dau V[0] = A visited. Cay BFS hien chi co root A (cac node con bi hidden). Frontier = [A]. Tree SVG node count = 1.
Step 3 / 16
Vong 1: dequeue A. Thuc hien danh gia hang xom cua A trong G: B va C. Ca hai chua visited –> se revive chung trong cay BFS (doi state tu hidden thanh visible).
Step 4 / 16
Tham B: revive T.node[B] (hidden -> current) va canh cay A-B. Enqueue B, mark visited. Canh A-B trong G to "good" vi day la tree edge. Tree SVG node count = 2.
Step 5 / 16
Tham C: revive T.node[C] va canh cay A-C. Enqueue C, mark visited. Frontier sau vong 1 = [B, C]. Tree BFS co 3 node, do sau 1.
Step 6 / 16
Vong 2: dequeue B. Hang xom cua B trong G: A (da visited, bo qua) va D. D chua visited –> se revive trong cay lam con cua B.
Step 7 / 16
Tham D: revive T.node[D] va canh cay B-D. Enqueue D. Frontier = [C, D]. Cay BFS gio sau 2 tang. Tree SVG node count = 4.
Step 8 / 16
Vong 3: dequeue C. Hang xom cua C: A (visited), D (visited!), E (chua). Canh C-D la canh cho (non-tree edge) – BFS khong them no vao cay BFS vi D da co cha la B.
Step 9 / 16
Canh (C,D) bi "dim" trong G – day la canh khong thuoc cay BFS. Trong do thi vo huong, cac non-tree edge chi co the la canh cho (cross edge) trong cung tang +/- 1. Day la mot tinh chat quan trong cua BFS tree.
Step 10 / 16
Tham E: revive T.node[E] va canh cay C-E. Enqueue E. Frontier = [D, E]. Tree SVG node count = 5 sau vong 3.
Step 11 / 16
Vong 4: dequeue D. Hang xom cua D: B (visited), C (visited), F (chua). Chi F duoc them vao cay.
Step 12 / 16
Tham F: revive T.node[F] va canh cay D-F. Enqueue F. Frontier = [E, F]. Tree SVG node count = 6 – day du moi dinh cua G.
Step 13 / 16
Vong 5: dequeue E. Hang xom cua E: C (visited) va F (visited). Khong them canh cay nao. Canh E-F la canh cho trong cung tang 3.
Step 14 / 16
Canh (E,F) bi "dim" – non-tree edge thu hai. Trong BFS tree voi 6 dinh, co 5 tree edge (cay spanning) va 2 canh du thua trong 7 canh ban dau. Cay BFS luon la spanning tree neu G lien thong.
Step 15 / 16
Vong 6: dequeue F. Hang xom: D (visited), E (visited). Khong co node moi. Queue rong –> BFS ket thuc.
Step 16 / 16
Ket thuc: cay BFS hoan chinh co 6 node (A la root, B/C tang 1, D/E tang 2, F tang 3 qua D). Toan bo canh "good" trong G tao thanh spanning tree; canh "dim" la cross edge. Khoang cach BFS(v) = do sau cua v trong cay. Day la tinh chat quan trong nhat cua BFS: duong di ngan nhat tren do thi khong trong so.