A. Phương pháp duyệt đồ thị theo chiều sâu:
Mẫu thầy đưa ra.

for all x Э V Đx(x) : = false;
Proc. DS (v: Đỉnh xuất phát)
1. Đx(v) : = true;
2. For all x Э Danh sách kề (v);
          IF !Đx(x) DS (x)

B. Phương pháp duyệt đồ thị theo chiều rộng:
Mẫu thầy đưa ra.
for all x Э V Đx(x) : = false;
Proc. DR (v: Đỉnh xuất phát)
Enqueue (v, HĐ)
Đx(v) :=True;
While (HĐ ≠ Ø )
                    a. u:=front (HĐ); Dequeue (HĐ);
                    for all x Э Danh sách kề (u)
                                        if !Đx(x) then
                                                            Đx(x) := True;
                                                            Enqueue (x, HĐ);

Áp dụng phần trên để giải vào bài cụ thể.
Đề thầy ra:
- Đồ thị G liên thông, có n đỉnh được đánh số từ 1 đến n, cho bởi ma trận kề A = a(i,j) Viết thủ tục xây dựng cây khung của đồ thị n x n dựa trên phép duyệt ưu tiên chiều rộng.

A) Mô tả cấu trúc câu khung:
T = array (1.. n-1) of Edge;
Edge = record
          d, c: tên đỉnh;
          end;
B) Thuật toán
E' = Ø; Q = Ø;
          1) FOR i = 1 TO n DO Đx(i) : = false;
          2)u là đỉnh xuất phát
          3) Đx(u) : = true;
          4) ENQUEUE(u, Q);
          5)WHILE Q ≠ Ø DO
                    a) x = TOP(Q); DEQUEUE(Q);
                    b) FOR j = 1 TO n DO
                              IF A(x, j) = 1 & Đx(j) THEN
                                        i) E' = E' + (x, j)
                                        ii) Đx(j) = True
                                        iii) ENQUEUE(j, Q);

2. Trường hợp tiếp theo đề thầy ra:
- Đồ thị G, có n đỉnh 1 -n được cho bởi ma trận A(i,j) Viết
thủ tục dựa trên phép tì kiếm ưu tiên chiều sâu để liệt kê các đỉnh tìm
kiếm của đồ thị.

Ở đây G không nhắc đến liên thông, nên thủ tục chỉ cần đôi dòng, gọi thủ tục ở phần trên đã viết:
For i := 1 to n
IF (!Đx(i)           DS (i);

3. Trường hợp tiếp theo đề thầy ra:
Đếm số vùng liên thông của đồ thị G:

d=0;
For i = 1 to n
                    IF (!Đx(i))
                                        DS (i);
                                        d++
Output d;

4. Trường hợp tiếp theo đề thầy ra:
Đồ thị G có n đỉnh liên thông (1-n) cho bởi danh sách kề, có cấu trúc:
DS [1..n] of List
List: ^ Kề;
          Kề = Record
          t: Tên đỉnh;
          next: List;
          end.

Viết thủ tục liệt kê tên các đỉnh dựa trên phép tìm kiếm ưu tiên chiều rộng.

For all x Э DsachKe (u) , P:= DS (u);
Proc. DR (v: Đỉnh xuất phát)
Enqueue (v, HĐ)
Đx(v) :=True;
While (HĐ ≠ Ø )
                    a. u:=front (HĐ); Dequeue (HĐ);
                    While (P ≠ Nil)
                                        a. x:= P^.t
                                        if !Đx(x) then
                                                            Đx(x) := True;
                                                            Enqueue (x, HĐ);
                    b. P:=P^.Next

Đề thầy ra tiếp:
Làm các bài tập trên thật thành thạo với danh sách liên kết và phương pháp duyệt theo chiều sâu. Bạn nào giải xong thì post lên chia sẻ nha. Đồng thời cần thêm bình giảng viên để mọi người hiểu chắc chắn nội dung này. Đây là nội dung chắc chắn có trong đề thi với nhóm điểm cao 3,5-5 điểm.

Tôi nghĩ là đ/c Admin chưa áp dụng đúng thuật toán duyệt theo chiều rộng đối với đầu bài cho là mảng danh sách liên kết, thể hiện là danh sách kề.
Vẫn áp dụng cấu trúc của duyệt theo chiều rộng. Nhưng nhớ rằng : input đầu bài là DS(1..n) cho nên thủ tục có thể viết như sau:

for i := 1 to n do Đx(i) := false;
for all P Э DS[1..n] do
Proc. DR (P: danh sách xuất phát)
x := P^.t;
Enqueue (x, HĐ);
if Đx(x) = false then
          a, Đx(x) :=True;
          b, Output(x);
While (HĐ ≠ Ø ) do
          1. u:=front (HĐ); Dequeue (HĐ);
          2. While (P ≠ Nil) do
a. x:= P^.t;
b.if !Đx(x) then
          Đx(x) := True; Output(x);
          Enqueue (x, HĐ);
c. P:=P^.Next;

Bài tập thầy yêu cầu:
Cho đồ thị G (V, E) với /V/ = n, /E/ = m các đỉnh được đánh số 1..n các canh được cho bởi mảng.
DS: array [1..m] of cạnh
cạnh = record
          đ, c: tên đỉnh
          end;
Viết thủ tục duyệt đồ thị theo chiều rộng, chiều sâu

- Duyệt theo chiều sâu:

          + Thủ tục con
          proc DS (u: tên đỉnh);
                              1. ĐX (u): = true;
                              2. viet (u);
                              for i: = 1 to n do
                                                  if ke(u, i) and ĐX (i) = false then DS (i)
          Function ke (x, y: tên đỉnh): boolean;
                              1. tg: false; k:=1;
                              2. while not tg and k ≤ m do
                                                  if DS[k].đ = x and DS[k].c = y then
                                                                                tg = true
                                                  k:++
                              3.ke: = tg or k ≤ m+1

          + Thủ tục chính
                    Proc. DFS (G);
                                                  1. for i := 1 to n do ĐX (i): = false
                                                  2. u: = đỉnh xuất phát
                                                  3. DS (u)

Admin đã viết:4. Trường hợp tiếp theo đề thầy ra:
Đồ thị G có n đỉnh liên thông (1-n) cho bởi danh sách kề, có cấu trúc:
DS [1..n] of List
List: ^ Kề;
          Kề = Record
          t: Tên đỉnh;
          next: List;
          end.

Viết thủ tục liệt kê tên các đỉnh dựa trên phép tìm kiếm ưu tiên chiều rộng.

For all x Э DsachKe (u) , P:= DS (u);
Proc. DR (v: Đỉnh xuất phát)
Enqueue (v, HĐ)
Đx(v) :=True;
While (HĐ ≠ Ø )
                    a. u:=front (HĐ); Dequeue (HĐ);
                    While (P ≠ Nil)
                                        a. x:= P^.t
                                        if !Đx(x) then
                                                            Đx(x) := True;
                                                            Enqueue (x, HĐ);
                    b. P:=P^.Next

- Theo tôi thì câu lệnh P:= DS (u); nên gán trong dòng lệnh (a). Vì khi lấy đỉnh u từ hàng đợi ra, ta mới xét các danh sách kề của u. Còn nếu gán P:= DS (u); ở đầu tiên thì chỉ duyệt được mỗi thằng v - là đỉnh đầu tiên và những đỉnh kề v thôi, còn những đỉnh không kề v thì không được đụng đến.

- Tiếp nữa câu lệnh P:=P^.Next phải nằm trong vòng while.

- Output?


1.
          for x:=1 to n do Đx(x):=false;

2.
          v:= đỉnh xuất phát; write (v);
          Đx(v) :=True;
          Enqueue (v, HĐ);

3.
          While (HĐ ≠ Ø )
                    u:=front (HĐ); Dequeue (HĐ);
                    P:=DS(u);
                    While (P ≠ Nil)
                              x:= P^.t;
                              if !Đx(x) then
                                        Đx(x) := True;   write (x);                   
                                        Enqueue (x, HĐ);
                              P:=P^.Next;

Hi. Bài 7 a.Phương viết đúng rồi
[You must be registered and logged in to see this image.]

Anh phương viết chuẩn rồi đấy.

Bài toán trên duyệt theo chiều sâu:
1. For i : = 1 to n do Đx(i) := False
2. Procedure D_S(u: đỉnh xuất phát);
Đx(u) := True;
Write(u);
P := DS[u];
While (P # Nil) do
x := P^.t;
If !Đx(x) then D_S(x);
P := P.next;

Lê Văn Đạt

LeVanDat đã viết:Tôi nghĩ là đ/c Admin chưa áp dụng đúng thuật toán duyệt theo chiều rộng đối với đầu bài cho là mảng danh sách liên kết, thể hiện là danh sách kề.
Vẫn áp dụng cấu trúc của duyệt theo chiều rộng. Nhưng nhớ rằng : input đầu bài là DS(1..n) cho nên thủ tục có thể viết như sau:

for i := 1 to n do Đx(i) := false;
for all P Э DS[1..n] do
Proc. DR (P: danh sách xuất phát)
x := P^.t;
Enqueue (x, HĐ);
if Đx(x) = false then
a, Đx(x) :=True;
b, Output(x);
While (HĐ ≠ Ø ) do
1. u:=front (HĐ); Dequeue (HĐ);
2. While (P ≠ Nil) do
a. x:= P^.t;
b.if !Đx(x) then
Đx(x) := True; Output(x);
Enqueue (x, HĐ);
c. P:=P^.Next;

Theo tôi nghĩ đ/c Đạt đang có những nhầm lẫn rất cơ bản ở đây:
1. Thuật toán DR luôn bắt đầu từ 1 đỉnh xuất phát chứ không phải danh sách xuất phát nên câu lệnh:
Proc. DR (P: danh sách xuất phát) là không đúng.
2. Đây là thuật toán loang: đầu tiên đánh dấu đỉnh xuất phát và cho vào hàng đợi. Lấy lần lượt các đỉnh ở đầu hàng đợi ra duyệt. Khi duyệt mỗi đỉnh, ta xét danh sách kề của nó, nếu các đỉnh trong danh sách kề chưa được xét thì đánh dấu đã xét và cho vào hàng đợi. Lấy cho đến khi hàng đợi rỗng. Quá trình này chỉ được làm 1 lần, không phải lặp đi lặp lại nên không viết:
for all P Э DS[1..n] do
Proc. DR (P: danh sách xuất phát)

Đ/c Admin viết đúng rồi, chỉ thiếu các lệnh output đỉnh sau khi đánh dấu đã xét thôi.