Tìm kiếm ưu tiên chiều rộng. Pascal

Tìm kiếm ưu tiên chiều rộng , hay còn gọi là “loang”, là một trong những thuật toán duyệt đồ thị đơn giản nhất. Ý tưởng của nó được sử dụng trong nhiều thuật toán, chẳng hạn thuật toán Prim tìm cây khung nhỏ nhất, thuật toán Dijkstra tìm đường đi ngắn nhất, v.v...
Loang chủ yếu được sử dụng để tìm đường đi ngắn nhất theo số cạnh giữa hai đỉnh của một đồ thị. Ta hình dung từ một đỉnh nguồn s, ban đầu thuật toán loang khám phá các đỉnh đến được từ s, đó là lớp thứ nhất, sau đó lại khám phá các đỉnh chưa thăm và đến được từ lớp thứ nhất, đó là lớp thứ hai, v.v... Nghĩa là các đỉnh đến từ có khoảng cách k từ s luôn được khám phá trước các đỉnh có khoảng cách k+1 từ s.
Sau đây là mã giả của thuật toán loang: (thực ra là mã Pascal)
For i:=1 to n do {n là số đỉnh}
            Trace[i]:=0;
Trace[s]:=-1; {s là đỉnh nguồn}
d[s]:=0; {d[i] là khoảng cách từ nguồn đến đỉnh i}
i:=1; j:=1; q[i]:=s; {q là hàng đợi}
While i<=j do
Begin
            For k  Adj[q[i]] do
                        If Trace[k]=0 then
                        Begin
                                    Trace[k]:=q[i];
                                    D[k]:=D[q[i]]+1;
                                    Inc(j);
                                    q[j]:=k;
                        End;
            Inc(i);
End;
Về mặt trực quan,  ta thấy thuật toán loang luôn tìm được đường đi ngắn nhất theo số cạnh giữa hai đỉnh của một đồ thị. Nhưng thực ra, cũng cần phải chứng minh điều này. Dưới đây là một số bổ đề, hướng chứng minh:
Ký hiệu s,v) là số cạnh ít nhất trên một đường đi nào đó giữa s và v, giá trị này còn được gọi là khoảng cách giữa s và v. Nếu không có đường đi thì s,vMột đường đi từ s đến v có số cạnh là s,v) được gọi là đường đi ngắn nhất (theo số cạnh) giữa s và v.
Bổ đề 1: Với mọi cạnh (u,v) thuộc G, ta có s,v)= s,u)+1
Bổ đề 2: Sau khi kết thúc thuật toán loang, với mọi đỉnh v giá trị d[v] trả về thỏa d[vs,v)
Chứng minh: có thể quy nạp theo số phép toán đẩy vào hàng đợi
Bổ đề 3: Giả sử trong qúa trình thực hiện thuật toán loang, hàng đợi Q chứa các đỉnh v1, v2, ... , vr, với v1 ở đầu hàng đợi và vr ở cuối. Thế thì d[vr] ≤ d[v1] + 1 và d[vi ] ≤ d[vi+1] với mọi i = 1, 2,..., r - 1.
Chứng minh: có thể quy nạp theo số phép toán hàng đợi
Hệ qủa 1: Giả sử đỉnh vi và vj được đưa vào hàng đợi trong qúa trình thực hiện thuật toán loang, và vi được đưa vào trước vj, thế thì d[vi] ≤ d[vj] ngay khi vj được đưa vào hàng đợi
Chứng minh: trực tiếp từ bổ đề 3 và tính chất mỗi đỉnh chỉ nhận giá trị d nhiều nhất một lần
Định lý: Sau khi kết thúc thuật toán loang,  d[v]= s,v) với mọi đỉnh v thuộc G
Chứng minh:
Phản chứng. Gọi v là đỉnh có giá trị  s,v) nhỏ nhất mà bị gán sai nhãn d[v], từ đó suy ra điều mâu thuẫn
Câu hỏi:
Cho G=(V,E) là một đồ thị vô hướng liên thông. Hãy viết chương trình tìm một đường đi trong G qua mỗi cạnh đúng một lần theo mỗi hướng.
Một số bài tập áp dụng
Biến đổi từ
Cho một từ điển (bao gồm một số từ). Từ một từ ta có thể thay đổi một chữ cái để thu được một từ khác cũng trong từ điển. Như vậy từ này có thể biến thành từ kia bằng cách thực hiện một số phép biến đổi. Ví dụ từ “spice” có thể biến đổi thành từ “stock” như sau: spice, slice, slick, stick, stock.
Yêu cầu: cho một số cặp từ, gồm từ nguồn và từ đích. Với mỗi cặp từ, hãy xác định số phép biến đổi ít nhất để từ từ nguồn thu được từ đích.
Giới hạn: từ điển chứa không qúa 200 từ
Hướng dẫn: đây là bài toán loang đơn giản. Mỗi từ là một đỉnh của