View Single Post
Old 01-01-1970, 07:00 AM   #5
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Default

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
Code:
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).
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog

thay đổi nội dung bởi: myhanh, 03-06-2008 lúc 09:52 AM.
myhanh is offline   Trả Lời Với Trích Dẫn
Đã có 2 thành viên gửi lời cám ơn đến myhanh vì bạn đã đăng bài:
Aidanmix (07-02-2017), Fajedgeaidele (26-11-2016)