Thuật toán tìm kiếm chiều rộng

Tìm kiếm ưu tiên chiều rộng - Một số bài tập áp dụng

Ngô Minh Đức

Trình bày sơ lược

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);