BFS và DFS

[ductam]

BFS (Breadth First Search):
BFS có rất nhiều ứng dụng trong lý thuyết đồ thị và trong các kì thi OLP Sinh viên cũng như các kì thi lập trình ACM/ICPC.
Mình xin nói sơ qua về bài toán như sau:

Cho đồ thị G=(V,E) có N đỉnh và m cạnh hai chiều hay một chiều là tùy theo bài toán mình xét. Vấn đề đơn giản đặt ra là giữa hai đỉnh u, v có đường đi không?
Không mất tính tổng quát ta bắt đầu duyệt từ đỉnh u, duyệt qua tất cả các đỉnh mà từ u có thể đi đến trực tiếp bằng một cạnh nối. Với mỗi đỉnh thỏa mãn, ta bỏ đỉnh đó vào queue. Như vậy đầu tiên ta bỏ đi u vào queue. Lấy đỉnh u ra và duyệt qua tất cả các đỉnh nối với đỉnh u bằng một cạnh nối , ném tất cả các đỉnh tìm được vào queue. Cứ như thế đến khi nào queue rỗng thì dừng. Vấn đề đặt ra là làm sao ta biết đỉnh v đã được duyệt chưa. Nếu đỉnh v chưa được duyệt chứng tỏ giữa u-v không có đường đi. Còn đỉnh v đã được duyệt thì giữa u-v có đường nối. Như vậy trong kỹ thuật lập trình đơn giản ta khai báo mảng free[maxN] trong đó free[i]=0 thì đỉnh i đã được thăm, free[i]=1 thì đỉnh i chưa được thăm. Ban đầu ta khởi trị thì free[i]=1, i=1..N vì chưa có đỉnh nào được thăm

<hôm sau viết tiếp>