Giải thuật và lập trình: §3. Các thuật toán tìm kiếm trên đồ thị

3.1. BÀI TOÁN

Cho đồ thị G = (V, E). u và v là hai đỉnh của G. Một đường đi (path) độ dài l từ đỉnh u đến đỉnh v là dãy (u = x0, x1, ..., xl = v) thoả mãn (xi, xi+1) ∈ E với ∀i: (0 ≤ i < l).

Đường đi nói trên còn có thể biểu diễn bởi dãy các cạnh: (u = x0, x1), (x1, x2), ..., (xl-1, xl = v).

Đỉnh u được gọi là đỉnh đầu, đỉnh v được gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối gọi là chu trình (Circuit), đường đi không có cạnh nào đi qua hơn 1 lần gọi là đường đi đơn, tương tự ta có khái niệm chu trình đơn.

Ví dụ: Xét một đồ thị vô hướng và một đồ thị có hướng trong Hình 55:

Trên cả hai đồ thị, (1, 2, 3, 4) là đường đi đơn độ dài 3 từ đỉnh 1 tới đỉnh 4. (1, 6, 5, 4) không phải đường đi vì không có cạnh (cung) nối từ đỉnh 6 tới đỉnh 5.

Một bài toán quan trọng trong lý thuyết đồ thị là bài toán duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát nào đó. Vấn đề này đưa về một bài toán liệt kê mà yêu cầu của nó là không được bỏ sót hay lặp lại bất kỳ đỉnh nào. Chính vì vậy mà ta phải xây dựng những thuật toán cho phép duyệt một cách hệ thống các đỉnh, những thuật toán như vậy gọi là những thuật toán tìm kiếm trên đồ thị và ở đây ta quan tâm đến hai thuật toán cơ bản nhất: thuật toán tìm kiếm theo chiều sâu và thuật toán tìm kiếm theo chiều rộng cùng với một số ứng dụng của chúng.

Lưu ý:

Những cài đặt dưới đây là cho đơn đồ thị vô hướng, muốn làm với đồ thị có hướng hay đa đồ thị cũng không phải sửa đổi gì nhiều.

Dữ liệu về đồ thị sẽ được nhập từ file văn bản GRAPH.INP. Trong đó:

Dòng 1 chứa số đỉnh n (≤ 100), số cạnh m của đồ thị, đỉnh xuất phát S, đỉnh kết thúc F cách nhau một dấu cách.

m dòng tiếp theo, mỗi dòng có dạng hai số nguyên dương u, v cách nhau một dấu cách, thể hiện có cạnh nối đỉnh u và đỉnh v trong đồ thị.

Kết quả ghi ra file văn bản PATH.OUT

Danh sách các đỉnh có thể đến được từ S.

Đường đi từ S tới F:

3.2. Thuật toán tìm kiếm theo chiều sâu (DEPTH FIRST SEARCH)

3.2.1. Cài đặt đệ quy

Tư tưởng của thuật toán có thể trình bày như sau: Trước hết, mọi đỉnh x kề với S tất nhiên sẽ đến được từ S. Với mỗi đỉnh x kề với S đó thì tất nhiên những đỉnh y kề với x cũng đến được từ S... Điều đó gợi ý cho ta viết một thủ tục đệ quy DFS(u) mô tả việc duyệt từ đỉnh u bằng cách thông báo thăm đỉnh u và tiếp tục quá trình duyệt DFS(v) với v là một đỉnh chưa thăm kề với u.

Để không một đỉnh nào bị liệt kê tới hai lần, ta sử dụng kỹ thuật đánh dấu, mỗi lần thăm một đỉnh, ta đánh dấu đỉnh đó lại để các bước duyệt đệ quy kế tiếp không duyệt lại đỉnh đó nữa Để lưu lại đường đi từ đỉnh xuất phát S, trong thủ tục DFS(u), trước khi gọi đệ quy DFS(v) với v là một đỉnh kề với u mà chưa đánh dấu, ta lưu lại vết đường đi từ u tới v bằng cách đặt TRACE[v] := u, tức là TRACE[v] lưu lại đỉnh liền trước v trong đường đi từ S tới v. Khi quá trình tìm kiếm theo chiều sâu kết thúc, đường đi từ S tới F sẽ là:

F ← p1 = Trace[F] ← p2 = Trace[p1] ←... ← S.

procedure DFS(u∈V);

begin
  < 1. Thông báo tới được u >;
  < 2. Đánh dấu u là đã thăm (có thể tới được từ S)>;
  < 3. Xét mọi đỉnh v kề với u mà chưa thăm, với mỗi đỉnh v đó >;
  begin
    Trace[v] := u; {Lưu vết đường đi, đỉnh mà từ đó tới v là u}
    DFS(v); {Gọi đệ quy duyệt tương tự đối với v}
  end;
end;

begin {Chương trình chính}
  < Nhập dữ liệu: đồ thị, đỉnh xuất phát S, đỉnh đích F >;
  < Khởi tạo: Tất cả các đỉnh đều chưa bị đánh dấu >;
  DFS(S);
  < Nếu F chưa bị đánh dấu thì không thể có đường đi từ S tới F >;
  < Nếu F đã bị đánh dấu thì truy theo vết để tìm đường đi từ S tới F >;
end.

P_4_03_1.PAS * Thuật toán tìm kiếm theo chiều sâu

program Depth_First_Search_1;
const
  InputFile = 'GRAPH.INP';
  OutputFile = 'PATH.OUT';
  max = 100;
var
  a: array[1..max, 1..max] of Boolean; {Ma trận kề của đồ thị}
  Free: array[1..max] of Boolean; {Free[v] = True ⇔ v chưa được thăm đến}
  Trace: array[1..max] of Integer; {Trace[v] = đỉnh liền trước v trên đường đi từ S tới v}
  n, S, F: Integer;
  fo: Text;

procedure Enter; {Nhập dữ liệu}
var
  i, u, v, m: Integer;
  fi: Text;
begin
  Assign(fi, InputFile);
  Reset(fi);
  FillChar(a, SizeOf(a), False); {Khởi tạo đồ thị chưa có cạnh nào}
  ReadLn(fi, n, m, S, F); {Đọc dòng 1 ra 4 số n, m, S và F}
  for i := 1 to m do {Đọc m dòng tiếp ra danh sách cạnh}
  begin
    ReadLn(fi, u, v);
    a[u, v] := True;
    a[v, u] := True;
  end;
  Close(fi);
end;

procedure DFS(u: Integer); {Thuật toán tìm kiếm theo chiều sâu bắt đầu từ đỉnh u}
var
  v: Integer;
  begin
    Write(fo, u, ', '); {Thông báo tới được u}
    Free[u] := False; {Đánh dấu u đã thăm}
    for v := 1 to n do
      if Free[v] and a[u, v] then {Với mỗi đỉnh v chưa thăm kề với u}
      begin
        Trace[v] := u; {Lưu vết đường đi: Đỉnh liền trước v trong đường đi từ S tới v là u}
        DFS(v); {Tiếp tục tìm kiếm theo chiều sâu bắt đầu từ v}
      end;
  end;

procedure Result; {In đường đi từ S tới F}
begin
  WriteLn(fo); {Vào dòng thứ hai của Output file}
  WriteLn(fo, 'Path from ', S, ' to ', F, ': ');
  if Free[F] then {Nếu F chưa đánh dấu thăm tức là không có đường}
    WriteLn(fo,'not found')
  else {Truy vết đường đi, bắt đầu từ F}
  begin
    while F <> S do
    begin
      Write(fo, F, '<-');
      F := Trace[F];
    end;
    WriteLn(fo, S);
  end;
end;

begin
  Enter;
  Assign(fo, OutputFile);
  Rewrite(fo);
  WriteLn(fo, 'From ', S, ' you can visit: ');
  FillChar(Free, n, True);
  DFS(S);
  Result;
  Close(fo);
end.

Chú ý:

Vì có kỹ thuật đánh dấu, nên thủ tục DFS sẽ được gọi ≤ n lần (n là số đỉnh).

Đường đi từ S tới F có thể có nhiều, ở trên chỉ là một trong số các đường đi. Cụ thể là đường đi có hứ tự từ điển nhỏ nhất.

Có thể chẳng cần dùng mảng đánh dấu Free, ta khởi tạo mảng lưu vết Trace ban đầu toàn 0, mỗi lần từ đỉnh u thăm đỉnh v, ta có thao tác gán vết Trace[v] := u, khi đó Trace[v] sẽ khác 0. Vậy việc kiểm tra một đỉnh v là chưa được thăm ta có thể kiểm tra Trace[v] = 0. Chú ý: ban đầu khởi tạo Trace[S] := -1 (Chỉ là để cho khác 0 thôi).

procedure DFS(u: Integer); {Cải tiến}
var
  v: Integer;
begin
  Write(u, ', ');
  for v := 1 to n do
    if (Trace[v] = 0) and A[u, v] then {Trace[v] = 0 thay vì Free[v] = True}
    begin
      Trace[v] := u; {Lưu vết cũng là đánh dấu luôn}
      DFS(v);
    end;
end;

Ví dụ: Với đồ thị sau đây, đỉnh xuất phát S = 1: quá trình duyệt đệ quy có thể vẽ trên cây tìm kiếm DFS sau (Mũi tên u→v chỉ thao tác đệ quy: DFS(u) gọi DFS(v)).

Hỏi: Đỉnh 2 và 3 đều kề với đỉnh 1, nhưng tại sao DFS(1) chỉ gọi đệ quy tới DFS(2) mà không gọi DFS(3) ?.

Trả lời: Đúng là cả 2 và 3 đều kề với 1, nhưng DFS(1) sẽ tìm thấy 2 trước và gọi DFS(2). Trong DFS(2) sẽ xét tất cả các đỉnh kề với 2 mà chưa đánh dấu thì dĩ nhiên trước hết nó tìm thấy 3 và gọi DFS(3), khi đó 3 đã bị đánh dấu nên khi kết thúc quá trình đệ quy gọi DFS(2), lùi về DFS(1) thì đỉnh 3 đã được thăm (đã bị đánh dấu) nên DFS(1) sẽ không gọi DFS(3) nữa.

Hỏi: Nếu F = 5 thì đường đi từ 1 tới 5 trong chương trình trên sẽ in ra thế nào ?.

Trả lời: DFS(5) do DFS(3) gọi nên Trace[5] = 3. DFS(3) do DFS(2) gọi nên Trace[3] = 2. DFS(2) do DFS(1) gọi nên Trace[2] = 1. Vậy đường đi là: 5 ← 3 ← 2 ←1.

Với cây thể hiện quá trình đệ quy DFS ở trên, ta thấy nếu dây chuyền đệ quy là: DFS(S) → DFS (u1) → DFS(u2) ... Thì thủ tục DFS nào gọi cuối dây chuyền sẽ được thoát ra đầu tiên, thủ tục DFS(S) gọi đầu dây chuyền sẽ được thoát cuối cùng, từ đây ta có ý tưởng mô phỏng dây chuyền đệ quy bằng một ngăn xếp (Stack).

3.2.2. Cài đặt không đệ quy

Khi mô tả quá trình đệ quy bằng một ngăn xếp, ta luôn luôn để cho ngăn xếp lưu lại dây chuyền duyệt sâu từ nút gốc (đỉnh xuất phát S).

<Thăm S, đánh dấu S đã thăm>;
<Đẩy S vào ngăn xếp>; {Dây chuyền đệ quy ban đầu chỉ có một đỉnh S}
repeat
  <Lấy u khỏi ngăn xếp>; {Đang đứng ở đỉnh u}
  if <u có đỉnh kề chưa thăm> then
  begin
    <Chỉ chọn lấy 1 đỉnh v, là đỉnh đầu tiên kề u mà chưa được thăm>;
    <Thông báo thăm v>;
    <Đẩy u trở lại ngăn xếp>; {Giữ lại địa chỉ quay lui}
    <Đẩy tiếp v vào ngăn xếp>; {Dây chuyền duyệt sâu được "nối" thêm v nữa}
  end;
  {Còn nếu u không có đỉnh kề chưa thăm thì ngăn xếp sẽ ngắn lại, tương ứng với sự lùi về của dây chuyền DFS}
until <Ngăn xếp rỗng>;

P_4_03_2.PAS * Thuật toán tìm kiếm theo chiều sâu không đệ quy
program Depth_First_Search_2;
const
  InputFile = 'GRAPH.INP';
  OutputFile = 'PATH.OUT';
  max = 100;
var
  a: array[1..max, 1..max] of Boolean;
  Free: array[1..max] of Boolean;
  Trace: array[1..max] of Integer;
  Stack: array[1..max] of Integer;
  n, S, F, Last: Integer;
  fo: Text;

procedure Enter;
var
  i, u, v, m: Integer;
  fi: Text;
begin
  Assign(fi, InputFile);
  Reset(fi);
  FillChar(a, SizeOf(a), False);
  ReadLn(fi, n, m, S, F);
  for i := 1 to m do
  begin
    ReadLn(fi, u, v);
    a[u, v] := True;
    a[v, u] := True;
  end;
  Close(fi);
end;

procedure Init; {Khởi tạo}
begin
  FillChar(Free, n, True); {Các đỉnh đều chưa đánh dấu}
  Last := 0; {Ngăn xếp rỗng}
end;

procedure Push(V: Integer); {Đẩy một đỉnh V vào ngăn xếp}
begin
  Inc(Last);
  Stack[Last] := V;
end;

function Pop: Integer; {Lấy một đỉnh khỏi ngăn xếp, trả về trong kết quả hàm}
begin
  Pop := Stack[Last];
  Dec(Last);
end;

procedure DFS;
var
  u, v: Integer;
begin
  Write(fo, S, ', ');
  Free[S] := False; {Thăm S, đánh dấu S đã thăm}
  Push(S); {Khởi động dây chuyền duyệt sâu}
  repeat
    {Dây chuyền duyệt sâu đang là S→ ...→ u}
    u := Pop; {u là điểm cuối của dây chuyền duyệt sâu hiện tại}
    for v := 1 to n do
      if Free[v] and a[u, v] then {Chọn v là đỉnh đầu tiên chưa thăm kề với u, nếu có:}
      begin
        Write(fo, v, ', ');
        Free[v] := False; {Thăm v, đánh dấu v đã thăm}
        Trace[v] := u; {Lưu vết đường đi}
        Push(u); Push(v); {Dây chuyền duyệt sâu bây giờ là S→ ...→ u→ v}
        Break;
      end;
  until Last = 0; {Ngăn xếp rỗng}
end;

procedure Result; {In đường đi từ S tới F}
begin
  WriteLn(fo); {Vào dòng thứ hai của Output file}
  WriteLn(fo, 'Path from ', S, ' to ', F, ': ');
  if Free[F] then {Nếu F chưa đánh dấu thăm tức là không có đường}
    WriteLn(fo,'not found')
  else {Truy vết đường đi, bắt đầu từ F}
  begin
    while F <> S do
    begin
      Write(fo, F, '<-');
      F := Trace[F];
    end;
    WriteLn(fo, S);
  end;
end;

begin
  Enter;
  Assign(fo, OutputFile);
  Rewrite(fo);
  WriteLn(fo, 'From ', S, ' you can visit: ');
  Init;
  DFS;
  Result;
  Close(fo);
end.

Ví dụ: Với đồ thị dưới đây (S = 1), Ta thử theo dõi quá trình thực hiện thủ tục tìm kiếm theo chiềusâu dùng ngăn xếp và đối sánh thứ tự các đỉnh được thăm với thứ tự từ 1st đến 6th trong cây tìm kiếm của thủ tục DFS dùng đệ quy.

Trước hết ta thăm đỉnh 1 và đẩy nó vào ngăn xếp.

Trên đây là phương pháp dựa vào tính chất của thủ tục đệ quy để tìm ra phương pháp mô phỏng nó.

Tuy nhiên, trên mô hình đồ thị thì ta có thể có một cách viết khác tốt hơn cũng không đệ quy: Thử nhìn lại cách thăm đỉnh của DFS: Từ một đỉnh u, chọn lấy một đỉnh v kề nó mà chưa thăm rồi tiến sâu xuống thăm v. Còn nếu mọi đỉnh kề u đều đã thăm thì lùi lại một bước và lặp lại quá trình tương tự, việc lùi lại này có thể thực hiện dễ dàng mà không cần dùng Stack nào cả, bởi với mỗi đỉnh u đã có một nhãn Trace[u] (là đỉnh mà đã từ đó mà ta tới thăm u), khi quay lui từ u sẽ lùi về đó.

Vậy nếu ta đang đứng ở đỉnh u, thì đỉnh kế tiếp phải thăm tới sẽ được tìm như trong hàm FindNext dưới đây:

function FindNext(u∈V): ∈V; {Tìm đỉnh sẽ thăm sau đỉnh u, trả về 0 nếu mọi đỉnh tới được từ S đều đã thăm}
begin
  repeat
    for (∀v ∈ Kề(u)) do
      if <v chưa thăm> then {Nếu u có đỉnh kề chưa thăm thì chọn đỉnh kề đầu tiên chưa thăm để thăm tiếp}
      begin
        Trace[v] := u; {Lưu vết}
        FindNext := v;
        Exit;
      end;
      u := Trace[u]; {Nếu không, lùi về một bước. Lưu ý là Trace[S] được gán bằng n + 1}
      until u = n + 1;
      FindNext := 0; {ở trên không Exit được tức là mọi đỉnh tới được từ S đã duyệt xong}
end;

begin {Thuật toán duyệt theo chiều sâu}
  Trace[S] := n + 1;
  <Khởi tạo các đỉnh đều là chưa thăm>
  u := S;
  repeat
    <Thông báo thăm u, đánh dấu u đã thăm>;
    u := FindNext(u);
  until u = 0;
end;

3.3. Thuật toán tìm kiếm theo chiều rộng (BREADTH FIRST SEARCH)

3.3.1. Cài đặt bằng hàng đợi

Cơ sở của phương pháp cài đặt này là "lập lịch" duyệt các đỉnh. Việc thăm một đỉnh sẽ lên lịch duyệt các đỉnh kề nó sao cho thứ tự duyệt là ưu tiên chiều rộng (đỉnh nào gần S hơn sẽ được duyệt trước). Ví dụ: Bắt đầu ta thăm đỉnh S. Việc thăm đỉnh S sẽ phát sinh thứ tự duyệt những đỉnh (x1, x2, ..., xp) kề với S (những đỉnh gần S nhất). Khi thăm đỉnh x1 sẽ lại phát sinh yêu cầu duyệt những đỉnh (u1, u2 ..., uq) kề với x1. Nhưng rõ ràng các đỉnh u này "xa" S hơn những đỉnh x nên chúng chỉ được duyệt khi tất cả những đỉnh x đã duyệt xong. Tức là thứ tự duyệt đỉnh sau khi đã thăm x1 sẽ là:

(x2, x3..., xp, u1, u2, ..., uq).

Giả sử ta có một danh sách chứa những đỉnh đang "chờ" thăm. Tại mỗi bước, ta thăm một đỉnh đầu danh sách và cho những đỉnh chưa "xếp hàng" kề với nó xếp hàng thêm vào cuối danh sách. Chính vì nguyên tắc đó nên danh sách chứa những đỉnh đang chờ sẽ được tổ chức dưới dạng hàng đợi (Queue).

Mô hình của giải thuật có thể viết như sau:

Bước 1: Khởi tạo:

Các đỉnh đều ở trạng thái chưa đánh dấu, ngoại trừ đỉnh xuất phát S là đã đánh dấu.

Một hàng đợi (Queue), ban đầu chỉ có một phần tử là S. Hàng đợi dùng để chứa các đỉnh sẽ được duyệt theo thứ tự ưu tiên chiều rộng.

Bước 2: Lặp các bước sau đến khi hàng đợi rỗng:

Lấy u khỏi hàng đợi, thông báo thăm u (Bắt đầu việc duyệt đỉnh u)

Xét tất cả những đỉnh v kề với u mà chưa được đánh dấu, với mỗi đỉnh v đó:

Đánh dấu v.

Ghi nhận vết đường đi từ u tới v (Có thể làm chung với việc đánh dấu)

Đẩy v vào hàng đợi (v sẽ chờ được duyệt tại những bước sau)

Các thuật toán trên đồ thị

Bước 3: Truy vết tìm đường đi.

P_4_03_3.PAS * Thuật toán tìm kiếm theo chiều rộng dùng hàng đợi

program Breadth_First_Search_1;
const
  InputFile = 'GRAPH.INP';
  OutputFile = 'PATH.OUT';
  max = 100;
var
  a: array[1..max, 1..max] of Boolean;
  Free: array[1..max] of Boolean; {Free[v] ⇔ v chưa được xếp vào hàng đợi để chờ thăm}
  Trace: array[1..max] of Integer;
  Queue: array[1..max] of Integer;
  n, S, F, First, Last: Integer;
  fo: Text;

procedure Enter; {Nhập dữ liệu}
var
  i, u, v, m: Integer;
  fi: Text;
begin
  Assign(fi, InputFile);
  Reset(fi);
  FillChar(a, SizeOf(a), False);
  ReadLn(fi, n, m, S, F);
  for i := 1 to m do
  begin
    ReadLn(fi, u, v);
    a[u, v] := True;
    a[v, u] := True;
  end;
  Close(fi);
end;

procedure Init; {Khởi tạo}
begin
  FillChar(Free, n, True); {Các đỉnh đều chưa đánh dấu}
  Free[S] := False; {Ngoại trừ đỉnh S}
  Queue[1] := S; {Hàng đợi chỉ gồm có một đỉnh S}
  Last := 1;
  First := 1;
end;

procedure Push(V: Integer); {Đẩy một đỉnh V vào hàng đợi}
begin
  Inc(Last);
  Queue[Last] := V;
end;

function Pop: Integer; {Lấy một đỉnh khỏi hàng đợi, trả về trong kết quả hàm}
begin
  Pop := Queue[First];
  Inc(First);
end;

procedure BFS; {Thuật toán tìm kiếm theo chiều rộng}
var
  u, v: Integer;
begin
  repeat
    u := Pop; {Lấy một đỉnh u khỏi hàng đợi}
    Write(fo, u, ', '); {Thông báo thăm u}
    for v := 1 to n do
      if Free[v] and a[u, v] then {Xét những đỉnh v chưa đánh dấu kề u}
      begin
        Push(v); {Đưa v vào hàng đợi để chờ thăm}
        Free[v] := False; {Đánh dấu v}
        Trace[v] := u; {Lưu vết đường đi: đỉnh liền trước v trong đường đi từ S là u}
      end;
  until First > Last; {Cho tới khi hàng đợi rỗng}
end;

procedure Result; {In đường đi từ S tới F}
begin
  WriteLn(fo); {Vào dòng thứ hai của Output file}
  WriteLn(fo, 'Path from ', S, ' to ', F, ': ');
  if Free[F] then {Nếu F chưa đánh dấu thăm tức là không có đường}
    WriteLn(fo,'not found')
  else {Truy vết đường đi, bắt đầu từ F}
  begin
    while F <> S do
    begin
      Write(fo, F, '<-');
      F := Trace[F];
    end;
    WriteLn(fo, S);
  end;
end;

begin
  Enter;
  Assign(fo, OutputFile);
  Rewrite(fo);
  WriteLn(fo, 'From ', S, ' you can visit: ');
  Init;
  BFS;
  Result;
  Close(fo);
end.

Ví dụ: Xét đồ thị dưới đây, Đỉnh xuất phát S = 1.

Để ý thứ tự các phần tử lấy ra khỏi hàng đợi, ta thấy trước hết là 1; sau đó đến 2, 3; rồi mới tới 4, 5; cuối cùng là 6. Rõ ràng là đỉnh gần S hơn sẽ được duyệt trước. Và như vậy, ta có nhận xét: nếu kết hợp lưu vết tìm đường đi thì đường đi từ S tới F sẽ là đường đi ngắn nhất (theo nghĩa qua ít cạnh nhất)

3.3.2. Cài đặt bằng thuật toán loang

Cách cài đặt này sử dụng hai tập hợp, một tập "cũ" chứa những đỉnh "đang xét", một tập "mới" chứa những đỉnh "sẽ xét". Ban đầu tập "cũ" chỉ gồm mỗi đỉnh xuất phát, tại mỗi bước ta sẽ dùng tập "cũ" tính tập "mới", tập "mới" sẽ gồm những đỉnh chưa được thăm mà kề với một đỉnh nào đó của tập "cũ". Lặp lại công việc trên (sau khi đã gán tập "cũ" bằng tập "mới") cho tới khi tập cũ là rỗng:

Giải thuật loang có thể dựng như sau:

Bước 1: Khởi tạo

Các đỉnh khác S đều chưa bị đánh dấu, đỉnh S bị đánh dấu, tập "cũ" Old := {S}

Bước 2: Lặp các bước sau đến khi Old = ∅

Đặt tập "mới" New = ∅, sau đó dùng tập "cũ" tính tập "mới" như sau:

Xét các đỉnh u ∈ Old, với mỗi đỉnh u đó:

Thông báo thăm u

Xét tất cả những đỉnh v kề với u mà chưa bị đánh dấu, với mỗi đỉnh v đó:

Đánh dấu v

Lưu vết đường đi, đỉnh liền trước v trong đường đi S→v là u

Đưa v vào tập New

Gán tập "cũ" Old := tập "mới" New và lặp lại (có thể luân phiên vai trò hai tập này)

Bước 3: Truy vết tìm đường đi.

P_4_03_4.PAS * Thuật toán tìm kiếm theo chiều rộng dùng phương pháp loang

program Breadth_First_Search_2;
const
  InputFile = 'GRAPH.INP';
  OutputFile = 'PATH.OUT';
  max = 100;
var
  a: array[1..max, 1..max] of Boolean;
  Free: array[1..max] of Boolean;
  Trace: array[1..max] of Integer;
  Old, New: set of Byte;
  n, S, F: Byte;
  fo: Text;

procedure Enter; {Nhập dữ liệu}
var
  i, u, v, m: Integer;
  fi: Text;
begin
  Assign(fi, InputFile);
  Reset(fi);
  FillChar(a, SizeOf(a), False);
  ReadLn(fi, n, m, S, F);
  for i := 1 to m do
  begin
    ReadLn(fi, u, v);
    a[u, v] := True;
    a[v, u] := True;
  end;
  Close(fi);
end;

procedure Init;
begin
  FillChar(Free, n, True);
  Free[S] := False; {Các đỉnh đều chưa đánh dấu, ngoại trừ đỉnh S đã đánh dấu}
  Old := [S]; {Tập "cũ" khởi tạo ban đầu chỉ có mỗi S}
end;

procedure BFS; {Thuật toán loang}
var
  u, v: Byte;
begin
  repeat {Lặp: dùng Old tính New}
    New := [];
    for u := 1 to n do
      if u in Old then {Xét những đỉnh u trong tập Old, với mỗi đỉnh u đó:}
      begin
        Write(fo, u, ', '); {Thông báo thăm u}
        for v := 1 to n do
          if Free[v] and a[u, v] then {Quét tất cả những đỉnh v chưa bị đánh dấu mà kề với u}
          begin
            Free[v] := False; {Đánh dấu v và lưu vết đường đi}
            Trace[v] := u;
            New := New + [v]; {Đưa v vào tập New}
          end;
      end;
    Old := New; {Gán tập "cũ" := tập "mới" và lặp lại}
  until Old = []; {Cho tới khi không loang được nữa}
end;

procedure Result; {In đường đi từ S tới F}
begin
  WriteLn(fo); {Vào dòng thứ hai của Output file}
  WriteLn(fo, 'Path from ', S, ' to ', F, ': ');
  if Free[F] then {Nếu F chưa đánh dấu thăm tức là không có đường}
    WriteLn(fo,'not found')
  else {Truy vết đường đi, bắt đầu từ F}
  begin
    while F <> S do
      begin
        Write(fo, F, '<-');
        F := Trace[F];
      end;
    WriteLn(fo, S);
  end;
end;

begin
  Enter;
  Assign(fo, OutputFile);
  Rewrite(fo);
  WriteLn(fo, 'From ', S, ' you can visit: ');
  Init;
  BFS;
  Result;
  Close(fo);
end.

3.4. Độ phức tạp tính toán của BFS và DFS

Quá trình tìm kiếm trên đồ thị bắt đầu từ một đỉnh có thể thăm tất cả các đỉnh còn lại, khi đó cách biểu diễn đồ thị có ảnh hưởng lớn tới chi phí về thời gian thực hiện giải thuật:

Trong trường hợp ta biểu diễn đồ thị bằng danh sách kề, cả hai thuật toán BFS và DFS đều có độ phức tạp tính toán là O(n + m) = O(max(n, m)). Đây là cách cài đặt tốt nhất.

Nếu ta biểu diễn đồ thị bằng ma trận kề như ở trên thì độ phức tạp tính toán trong trường hợp này là O(n + n2) = O(n2).

Nếu ta biểu diễn đồ thị bằng danh sách cạnh, thao tác duyệt những đỉnh kề với đỉnh u sẽ dẫn tới việc phải duyệt qua toàn bộ danh sách cạnh, đây là cài đặt tồi nhất, nó có độ phức tạp tính toán là O(n.m).

Bài tập

Mê cung hình chữ nhật kích thước m x n gồm các ô vuông đơn vị. Trên mỗi ô ký tự:

O: Nếu ô đó an toàn

X: Nếu ô đó có cạm bẫy

E: Nếu là ô có một nhà thám hiểm đang đứng.

Duy nhất chỉ có 1 ô ghi chữ E. Nhà thám hiểm có thể từ một ô đi sang một trong số các ô chung cạnh với ô đang đứng. Một cách đi thoát khỏi mê cung là một hành trình đi qua các ô an toàn ra một ô biên. Hãy chỉ giúp cho nhà thám hiểm một hành trình thoát ra khỏi mê cung.