DAA - Cây kéo dài

A spanning tree là một tập hợp con của một Đồ thị vô hướng có tất cả các đỉnh được nối bằng số cạnh tối thiểu.

Nếu tất cả các đỉnh được nối trong một đồ thị, thì tồn tại ít nhất một cây khung. Trong một biểu đồ, có thể tồn tại nhiều hơn một cây khung.

Tính chất

Cây bao trùm không có bất kỳ chu trình nào.
Có thể đạt được bất kỳ đỉnh nào từ bất kỳ đỉnh nào khác.

Thí dụ

Trong biểu đồ sau, các cạnh được đánh dấu tạo thành một cây bao trùm.

Cây kéo dài tối thiểu

A Minimum Spanning Tree (MST)là một tập con các cạnh của một đồ thị vô hướng có trọng số được liên thông nối tất cả các đỉnh với tổng trọng số cạnh nhỏ nhất có thể. Để lấy MST, có thể sử dụng thuật toán Prim hoặc thuật toán Kruskal. Do đó, chúng ta sẽ thảo luận về thuật toán của Prim trong chương này.

Như chúng ta đã thảo luận, một biểu đồ có thể có nhiều hơn một cây bao trùm. Nếu cón số đỉnh, cây bao trùm phải có n - 1số cạnh. Trong bối cảnh này, nếu mỗi cạnh của đồ thị được liên kết với một trọng số và tồn tại nhiều hơn một cây bao trùm, chúng ta cần tìm cây bao trùm nhỏ nhất của đồ thị.

Hơn nữa, nếu tồn tại bất kỳ cạnh có trọng số trùng lặp nào, biểu đồ có thể có nhiều cây khung tối thiểu.

Trong biểu đồ trên, chúng ta đã chỉ ra một cây bao trùm mặc dù nó không phải là cây bao trùm tối thiểu. Chi phí của cây khung này là (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.

Chúng tôi sẽ sử dụng thuật toán của Prim để tìm cây bao trùm tối thiểu.

Thuật toán Prim

Thuật toán của Prim là một cách tiếp cận tham lam để tìm cây bao trùm tối thiểu. Trong thuật toán này, để tạo MST, chúng ta có thể bắt đầu từ một đỉnh tùy ý.

Algorithm: MST-Prim’s (G, w, r) 
for each u є G.V 
   u.key = ∞ 
   u.∏ = NIL 
r.key = 0 
Q = G.V 
while Q ≠ Ф 
   u = Extract-Min (Q) 
   for each v є G.adj[u] 
      if each v є Q and w(u, v) < v.key 
         v.∏ = u 
         v.key = w(u, v)

Hàm Extract-Min trả về đỉnh có chi phí cạnh tối thiểu. Chức năng này hoạt động trên min-heap.

Thí dụ

Sử dụng thuật toán Prim, chúng ta có thể bắt đầu từ bất kỳ đỉnh nào, hãy bắt đầu từ đỉnh 1.

Đỉnh 3 được kết nối với đỉnh 1 với chi phí cạnh tối thiểu, do đó cạnh (1, 2) được thêm vào cây khung.

Tiếp theo, cạnh (2, 3) được coi là mức tối thiểu trong số các cạnh {(1, 2), (2, 3), (3, 4), (3, 7)}.

Trong bước tiếp theo, chúng ta có (3, 4) và (2, 4)với chi phí tối thiểu. Cạnh(3, 4) được chọn ngẫu nhiên.

Theo cách tương tự, các cạnh (4, 5), (5, 7), (7, 8), (6, 8) và (6, 9)được chọn. Khi tất cả các đỉnh được thăm, bây giờ thuật toán dừng lại.

Chi phí của cây bao trùm là (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23. Không có cây bao trùm nào trong đồ thị này có chi phí nhỏ hơn 23.