Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Khác biệt giữa thuật toán Prim và Kruskal


Hiểu sự khác biệt giữa Prim và Kruskal để tìm Minimum Spanning Tree (MST).

Kruskal's algorithm cho MST

  • Đồ thị liên thông vô hướng → spanning tree là cây con kết nối mọi đỉnh.
  • Một đồ thị có nhiều spanning tree.
  • MST: spanning tree có trọng số nhỏ nhất hoặc bằng mọi spanning tree khác.
  • Trọng số spanning tree = tổng trọng số cạnh.
  • MST có thể xây từ đỉnh có trọng số nhỏ nhất.
  • Mỗi đỉnh duyệt một lần.
  • Nhanh trên đồ thị thưa (sparse).
  • Độ phức tạp O(E log V).
  • Làm việc được với disconnected components.

Các bước Kruskal

  • Sắp xếp cạnh theo trọng số tăng dần.
  • Chọn cạnh nhỏ nhất.
  • Kiểm tra có tạo chu trình với spanning tree hiện tại không.
  • Không tạo chu trình → thêm cạnh.
  • Ngược lại → bỏ qua.
  • Lặp lại cho đến khi spanning tree có V-1 cạnh.

Prim's algorithm MST

  • Tương tự Kruskal: greedy algorithm.
  • Bắt đầu spanning tree rỗng. Duy trì 2 tập đỉnh.
  • Tập 1: đỉnh đã trong MST. Tập 2: đỉnh chưa trong MST.
  • Mỗi bước: xét tất cả cạnh nối 2 tập, chọn cạnh trọng số nhỏ nhất.
  • Di chuyển đến đỉnh kia của cạnh đó, thêm vào tập MST.
  • MST có thể xây từ bất kỳ đỉnh nào.
  • Đỉnh có thể duyệt nhiều lần để lấy khoảng cách nhỏ nhất.
  • Độ phức tạp O(V^2), cải tiến O(E + log V) với Fibonacci heap.
  • Nhanh trên đồ thị đậm (dense).
  • Cho connected components, chỉ làm việc với connected graph.

Các bước Prim

  • Tạo mstSet theo dõi đỉnh đã trong MST.
  • Gán key value cho mọi đỉnh (INFINITE).
  • Key = 0 cho đỉnh đầu tiên để chọn trước.
  • Khi mstSet chưa chứa hết đỉnh:
    • Chọn đỉnh 'u' không trong mstSet, key nhỏ nhất.
    • Thêm 'u' vào mstSet.
    • Cập nhật key các đỉnh kề 'u': nếu trọng số u-v < key[v] → key[v] = weight(u,v).