[nguyenchican]

Nguyên văn bởi myhanh

CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
2.Cây khung của đồ thị:
Định nghĩa:
Giả sử G=(V,E) là đồ thị vô hướng liên thông. Cây T=(V,F), F là tập con của E được gọi là cây khung của đồ thị.
Áp dụng thuật toán tìm kiếm theo chiều rộng, chiều sâu để xây dựng cây khung của đồ thị vô hướng liên thông. Trong cả hai trường hợp mỗi khi ta đến được đỉnh mới u từ đỉnh v thì cạnh (v,u) sẽ được kết nạp vào cây khung

PROCEDURE STREE_DFS(v);
(* Tìm kiếm theo chiều sâu tìm cây khung T của đồ thị vô hướng liên thông G cho bởi danh sách kề, các biến chuaxet,ke,T là toàn cục*)
BEGIN
  chuaxet[v]:=false;
  FOR u in ke(v) DO
      IF chuaxet[u] THEN
          BEGIN
                T:=T U (v,u);
                   STREE_DFS(u);
          END;
END;
BEGIN
  FOR u in V DO chuaxet[u]:=true;
  T:=Ø;
  STREE_DFS(Root);
 END.

Bài tập:
Viết thủ tục STREE_BFS(v).

Nó giống Pascal thé trời