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).