Bài viết Thuật toán Prim: Tìm cây khung nhỏ nhất đã giới thiệu đến các bạn ý tưởng của thuật toán này cũng như từng bước chạy thuật toán. Tiếp theo sẽ là phần hướng dẫn cài đặt thuật toán Prim cho đồ thị vô hướng có trọng số bằng ngôn ngữ Java.
Chúng ta cùng nhắc lại ý tưởng cơ bản của thuật toán Prim:
- Bước 1: Chọn một đỉnh
vbất kỳ làm đỉnh bắt đầu và đưa đỉnhvvào cây khung. - Bước 2: Thêm tất cả các cạnh nối với
vvào danh sách cạnh đang xét . - Bước 3: Xét các cạnh trong danh sách đến khi hết:
- Bước 3.1: Lấy ra cạnh có trọng số nhỏ nhất nối từ
v1đến một đỉnhv2chưa nằm trong cây khung. Đưa cạnh này và đỉnhv2vào cây khung. - Bước 3.2: Đưa các cạnh nối từ đỉnh
v2đến các đỉnh chưa nằm trong cây khung vào danh sách cạnh đang xét.
- Bước 3.1: Lấy ra cạnh có trọng số nhỏ nhất nối từ
Ở bước lấy ra cạnh có trọng số nhỏ nhất trong số các cạnh đang xét, chúng ta sử dụng Min-PriorityQueue để lấy ra cạnh có trọng số nhỏ nhất.
Để hiện thực thuật toán Prim, chúng ta có thể sử dụng cấu trúc EdgeWeightedGraph để lưu trữ đồ thị vô hướng có trọng số mà mình có giới thiệu qua ở bài viết Tổng quan về đồ thị. Chúng ta định nghĩa trừu tượng các phương thức của một class làm nhiệm vụ tìm cây khung như sau:
public interface PrimMST {
Iterable<Edge> edges();
double weight();
}
Class LayzyPrimMST sẽ làm nhiệm vụ tìm cây khung nhỏ nhất cho đồ thị g với các phương thức:
- LazyPrimMST(EdgeWeightedGraph g): Constructor nhận vào đồ thị vô hướng có trọng số
gvà thực hiện tìm cây khung nhỏ nhất. - edges(): Trả về các cạnh của cây khung nhỏ nhất.
- weight(): Trả về trọng số của cây khung nhỏ nhất.
public class LazyPrimMST implements PrimMST {
public LazyPrimMST(EdgeWeightedGraph g) {
// to be implemented
}
@Override
public Iterable<Edge> edges() {
// to be implemented
}
@Override
public double weight() {
// to be implemented
}
Lúc này chúng ta có thể viết hàm main để test với đồ thị $G$ trong bài viết trước.
Đồ thị $G$
public static void main(String[] args) {
EdgeWeightedGraph g = new EdgeWeightedGraph(9);
g.addEdge(new Edge(0, 1, 2.5));
g.addEdge(new Edge(0, 2, 2.0));
g.addEdge(new Edge(0, 3, 2.1));
g.addEdge(new Edge(1, 4, 1.0));
g.addEdge(new Edge(2, 4, 0.6));
g.addEdge(new Edge(2, 5, 1.5));
g.addEdge(new Edge(3, 5, 2.5));
g.addEdge(new Edge(4, 6, 2.3));
g.addEdge(new Edge(5, 6, 1.9));
g.addEdge(new Edge(5, 7, 2.0));
g.addEdge(new Edge(6, 7, 1.8));
g.addEdge(new Edge(6, 8, 1.7));
g.addEdge(new Edge(7, 8, 2.0));
PrimMST prim = new LazyPrimMST(g);
System.out.println("Edges: ");
for (Edge e : prim.edges())
System.out.printf("%d-%d: %f\n", e.either(), e.other(e.either()), e.weight());
System.out.println("Weight: " + prim.weight());
}
Bên trong class LazyPrimMST, chúng ta định nghĩa một số field hỗ trợ cho việc tìm cây khung nhỏ nhất.
private boolean[] marked;
private LinkedList<Edge> mst;
private PriorityQueue<Edge> pq;
- marked: Mảng boolean đánh dấu một đỉnh đã được đưa vào cây khung hay chưa.
- mst: Danh sách các cạnh của cây khung.
- pq: Danh sách các cạnh dùng để xét sau mỗi bước chạy thuật toán. Sử dụng
PriorityQueueđể tiện lấy ra cạnh nhỏ nhất.
Thuật toán của chúng ta sẽ chạy trong constructor, ở đây chúng ta sẽ định nghĩa thêm hàm visit(G, v) làm nhiệm vụ đánh dấu đỉnh v đã được đưa vào cây khung và đưa các cạnh kề vào PriorityQueue.
Các bước thực hiện:
- 1. “Viếng thăm” đỉnh $0$.
- 2. Xét nếu queue vẫn có phần tử:
- 2.1. Lấy cạnh nhỏ nhất trong danh sách đang xét.
- 2.2. Nếu cả 2 đỉnh của cạnh này đều nằm trong cây khung thì bỏ qua.
- 2.3. Còn không thì đưa cạnh nhỏ nhất này vào cây khung.
- 2.4. “Viếng thăm” đỉnh chưa nằm trong cây khung.
public LazyPrimMST(EdgeWeightedGraph g) {
pq = new PriorityQueue<>(Edge::compareTo);
marked = new boolean[g.V()];
mst = new LinkedList<>();
visit(g, 0);
while (!pq.isEmpty()) {
Edge e = pq.poll();
int v = e.either(), w = e.other(v);
if (marked[v] && marked[w]) continue;
mst.add(e);
if (!marked[v]) visit(g, v);
if (!marked[w]) visit(g, w);
}
}
private void visit(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v))
if (!marked[e.other(v)]) pq.add(e);
}
Cài đặt các phương thức còn lại của class LazyPrimMST:
@Override
public Iterable<Edge> edges() {
return mst;
}
@Override
public double weight() {
return mst.stream().mapToDouble(Edge::weight).sum();
}
Sau khi hoàn tất, cùng test lại hàm main để xem kết quả:
Edges:
0-2: 2.000000
2-4: 0.600000
1-4: 1.000000
2-5: 1.500000
5-6: 1.900000
6-8: 1.700000
6-7: 1.800000
0-3: 2.100000
Weight: 12.6
Vẫn đúng với kết quả chạy từng bước ở bài viết trước phải không nào!
References
#Thuật #toán #Prim #Cài #đặt #thuật #toán
![[👨💻🇻🇳] Thuật toán Prim: Cài đặt thuật toán](https://2023-data-image.top1vps.com/wp-content/uploads/sites/3/2024/05/185499478_1664547703730541_4061818154429501193_n.png)
![[👨💻🇻🇳] Thuật toán Prim: Cài đặt thuật toán](https://2023-data-image.top1vps.com/wp-content/uploads/sites/3/2024/08/207231264_1406431406390621_3415461997845633627_n.jpg)
![[🆕🇻🇳] M.GAO – Quần áo – Thương hiệu [🆕Top1Vietnam🇻🇳] 👕 Top1Fashion 👗 “Áo Dây Nâu – Quần Loe”
Một thiết kế mang hơi thở nghệ thuật – nhẹ nhàng mà sắc sảo, gam màu đặc biệt tôn da
Chất liệu nhung da cao cấp mềm mịn, chiếc á , shares-0✔️ , likes-59❤️️ , date-2026-02-02 01:41:58🇻🇳🇻🇳🇻🇳📰🆕](https://2023-data-image.top1vps.com/wp-content/uploads/sites/3/2026/02/624256813_122160291560405122_7677996746828217607_n.jpg "[🆕🇻🇳] M.GAO – Quần áo – Thương hiệu [🆕Top1Vietnam🇻🇳] 👕 Top1Fashion 👗 “Áo Dây Nâu – Quần Loe”
Một thiết kế mang hơi thở nghệ thuật – nhẹ nhàng mà sắc sảo, gam màu đặc biệt tôn da
Chất liệu nhung da cao cấp mềm mịn, chiếc á , shares-0✔️ , likes-59❤️️ , date-2026-02-02 01:41:58🇻🇳🇻🇳🇻🇳📰🆕")
![[🆕🇻🇳] Biluxury – Thay đổi để thành công – Cửa hàng quần áo nam [🆕Top1Vietnam🇻🇳] 👕 Top1Fashion 👗 Hai người đàn ông, hai bộ suit, mỗi người một phong thái.
Bên trong lớp suit chỉn chu là áo len lông thỏ mềm mại, tạo cảm giác ấm áp nhưng vẫn giữ được fo , shares-0✔️ , likes-30❤️️ , date-2026-02-02 02:01:06🇻🇳🇻🇳🇻🇳📰🆕](https://2023-data-image.top1vps.com/wp-content/uploads/sites/3/2026/02/623849521_1300692635200920_8397577882596821681_n.jpg "[🆕🇻🇳] Biluxury – Thay đổi để thành công – Cửa hàng quần áo nam [🆕Top1Vietnam🇻🇳] 👕 Top1Fashion 👗 Hai người đàn ông, hai bộ suit, mỗi người một phong thái.
Bên trong lớp suit chỉn chu là áo len lông thỏ mềm mại, tạo cảm giác ấm áp nhưng vẫn giữ được fo , shares-0✔️ , likes-30❤️️ , date-2026-02-02 02:01:06🇻🇳🇻🇳🇻🇳📰🆕")
