Prim
Tags:
Hard
Skills:
PrimMST
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Theory Data Structure And Algorithms
No headings found
Related Posts
Theory Data Structure And Algorithms
What’s Prim
Thuật toán Prim là một thuật toán tham lam được sử dụng để tìm MST của một đồ thị liên thông, vô hướng và có trọng số. Thuật toán này đảm bảo tổng trọng số của các cạnh trong MST là nhỏ nhất
Nguyên lý hoạt động
Thuật toán Prim bắt đầu từ một đỉnh bất kỳ và mở rộng cây khung bằng cách thêm các cạnh có trọng số nhỏ nhất kết nối các đỉnh chưa được xét đến cây khung hiện tại. Quá trình này tiếp tục cho đến khi tất cả các đỉnh của đồ thị đều được bao gồm trong cây khung
Các bước thực hiện
- Khởi tạo
- Chọn một đỉnh bất kỳ làm điểm bắt đầu
- Tạo hai tập hợp: Tập hợp các đỉnh đã xét và tập hợp các cạnh trong cây khung
- Lặp lại
- Tìm cạnh có trọng số nhỏ nhất nối từ một đỉnh đã xét đến một đỉnh chưa xét
- Thêm cạnh này vào cây khung và đánh dấu đỉnh mới vừa được thêm vào
- Kết thúc
- Khi tất cả các đỉnh đã được thêm vào cây khung, thuật toán dừng lại
Độ phức tạp
- Sử dụng ma trận kề: O(v^2), với V là số đỉnh
- Sử dụng danh sách kề và cấu trúc dữ liệu như đống nhị phận: O((V + E)logV), với E là số cạnh
- Sử dụng đống Fibonacci: O(E + VlogV)
Ứng dụng
Thuật toán Prim thường được áp dụng trong
- Thiết kế mạng lưới (ví dụ: mạng máy tính, hệ thống đường giao thông).
- Các bài toán tối ưu hóa đồ thị trong khoa học máy tính và kỹ thuật5
So sánh với thuật toán Kruskal
Prim xây dựng cây khung bằng cách mở rộng từ một đỉnh ban đầu, trong khi Kruskal chọn các cạnh nhỏ nhất để xây dựng cây khung mà không phụ thuộc vào điểm bắt đầu
💡
Compare time and space complexity between Prim and Kruskal
Prim và Kruskal đều là các thuật toán tham lam để tìm cây khung nhỏ nhất (MST) của đồ thị. Tuy nhiên, chúng có sự khác biệt đáng kể về độ phức tạp thời gian và không gian, tùy thuộc vào cấu trúc đồ thị và cách triển khai.
- Time complexity
- Prim: Độ phức tạp phụ thuộc vào việc duy trì hàng đợi ưu tiên để chọn cạnh nhỏ nhất. Với heap Fibonacci, Prim có thể đạt độ phức tạp thấp hơn trong đồ thị dày đặc.
- Kruskal: Độ phức tạp chủ yếu bị chi phối bởi bước sắp xếp các cạnh, thường là O(ElogE). Điều này làm cho Kruskal hiệu quả hơn trong đồ thị thưa
- Space complexity
- Prim: Sử dụng thêm bộ nhớ để lưu trữ danh sách kề hoặc ma trận kề, cùng với hàng đợi ưu tiên.
- Kruskal: Cần bộ nhớ để lưu danh sách cạnh đã sắp xếp và cấu trúc dữ liệu Union-Find.
- Kết luân
- Nếu đồ thị dày đặc (nhiều cạnh), Prim thường vượt trội cả về thời gian lẫn không gian.
- Nếu đồ thị thưa (ít cạnh), Kruskal thường hiệu quả hơn về thời gian và sử dụng ít bộ nhớ hơn.
💡
E và V được dùng để biểu diễn các thành phần cơ bản của đồ thị
- V là gì?
- V là đại diện cho tập hợp các đỉnh (vertices) trong đồ thị
- Số lượng đỉnh trong đồ thị được gọi |V|, tức là số phần tử trong tập hợp V
- Vd đồ thị có 5 đỉnh, thì |V| = 5
- E là gì?
- E đại diện cho tập hợp các cạnh (edges) trong đồ thị
- Mỗi cạnh kết nối 2 đỉnh trong đồ thị và có thể có trọng số (weight)
- Số lượng cạnh trong đồ thị được gọi là |E|, tức là số phần tử trong tập hợp E
- VD: Nếu đồ thị có 7 cạnh, thì |E| = 7
- Mối quan hệ giữa E và V
- Trong một đồ thị đầy đủ (complete graph), mỗi cặp đỉnh đều được kết nối bởi một cạnh. Số lượng cạnh tối đa của đồ thị đầy đủ là:
- E = V(V - 1) / 2
- Trong đồ thị thưa (sparse graph), số lượng cạnh nhỏ hơn nhiều so với số lượng tối đa
- Ví dụ minh họa
- Đỉnh: V={A,B,C,D}, tức là ∣V∣=4∣V∣=4.
- Cạnh: E={(A,B),(B,C),(C,D)}, tức là ∣E∣=3∣
- V biểu diễn các điểm hoặc nút trong đồ thị.
- E biểu diễn các đường nối giữa các điểm.
Giả sử có một đồ thị như sau:
Trong trường hợp này: