Cây khung đồ thị là gì?
Định nghĩa của nó rất đơn giản: Cho đồ thị G = (V, E) cây khung của đồ thị T=(V, E') trong đó E' [You must be registered and logged in to see this image.] E. T liên thông và không có chu trình. Nếu /V/ = n (Đồ thị G có n đỉnh) → /E'/ = n - 1. T có n - 1 cạnh.

Tìm cây khung của đồ thị theo phép duyệt theo chiều rộng.

1. T = Ø ;
For all x Э V           ĐX(x) : = False;

2. Chọn đỉnh xuất phát u.
ĐX(u) : = true;
Hàng_đợi: = {u};

3. while Hàng_đợi ≠ Ø do
                    a. Lấy a từ hàng đợi
                    b. For all x Э ke+ (a) do
                                        if not ĐX(x) then
                                                  b1. T : = T U {(a, x)}
                                                  b2. ĐX(x) : = true
                                                  b3. Đưa x vào hàng đợi

Lưu ý:
Bài toán tìm cây kung của đồ thị thực chất là tìm tập cạnh. Trước khi trình bày thuật toán, bao giờ cũng phải đưa ra cấu trúc dữ liệu để lưu trữ cây khung. Thường cây khung được lưu dưới dạng mảng các cạnh (n - 1) cạnh.

T: array [1.. n-1] of Edge
          Edge = record
                    đ, c: tên đỉnh //đầu cuối
          end;

Bây giờ thử làm bài tập theo phần lý thuyết trên nha.
Một đề thi có câu sau:
Đồ thị G( V, t) liên thông có n đỉnh đánh số từ 1 đến n cho bởi ma trận kề A = (aij)_mxn. Viết thủ tục xây dựng cây khung của đồ thị dựa trên phép duyệt theo chiều rộng.

Bài làm
- Cấu trúc cây khung cần lưu trữ vào dạng dữ liệu sau:
T: array [1.. n-1] of Edge
          Edge = record
                    đ, c: tên đỉnh //đầu cuối
          end;

- Thủ tục tạo cây khung
proc Tìm_Cây_khung;
1. for i:=1 to n do ĐX(i):= False;
2. u:= Đỉnh_xuất_phát;
          ĐX(u) : = true;
          MakeNull (Q); EnQueue(u, Q) {Đưa u vào hàng đợi}
          k:=0;
3. while Empty (Q) = false do
                    a. a:= Front(Q); DeQueue(Q);
                    b. for x : =1 to n do
                                        if A[a, x] = 1 and ĐX(x) = false then
                                                            k:=k+1
                                                            T[k].đ = a; T[k].c = x;
                                                            ĐX(x) : = true;
                                                            EnQueue (x, Q);
4. Output (T).

Các đề cần phải làm hết sức thành thạo theo cách thức tương tự trên:
1. Đồ thị G( V, t) liên thông có n đỉnh đánh số từ 1 đến n và có m cạnh cho bởi danh sách cạnh:
          D: array [1..n] of Edge
                    Edge = record;
                              đ, c: Tên đỉnh;
                              End;
Viết thủ tục xây dựng cây khung.

3. Đơn đồ thị G = {V, E} vô hướng liên thông, có n đỉnh đánh số 1 .. n cho bởi danh sách kề.
DSK = Record
                    m: Số cạnh liên thuộc;
                    A: array [1..m] of Integer;
                    End;

DS: array [1..n] of DSK

Viết thủ tục chi tiết xây dựng cây khung của đồ thị G dựa trên phép duyệt ưu tiên chiều rộng. Cây khung phải lưu vào danh sách:
List [1..n] of Edge
          Edge = Record
                    đ, c: Tên đỉnh;
          End;

Còn Tìm cây khung của đồ thị theo phép duyệt theo chiều sâu thì sao vậy Admin :D
Admin có thể trình bày theo đúng cách thày Tĩnh được không?

dacminhm đã viết:Còn Tìm cây khung của đồ thị theo phép duyệt theo chiều sâu thì sao vậy Admin :D
Admin có thể trình bày theo đúng cách thày Tĩnh được không?

Chắc là thay hàng đợi bằng ngăn xếp là được thì phải?