Cài Đặt Thuật Toán Prim C++

     

Bài viết Thuật toán Prim: kiếm tìm cây khung bé dại nhất đã ra mắt đến chúng ta ý 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 sau sẽ là phần phía dẫn setup thuật toán Prim đến đồ thị vô hướng gồm trọng số bằng ngữ điệu Java.

Bạn đang xem: Cài đặt thuật toán prim c++

Mục lục 3. Thiết lập thuật toán. 1. Nhắc lại thuật toán

Chúng ta thuộc nhắc lại ý tưởng phát minh cơ bạn dạng của thuật toán Prim:

Bước 1: lựa chọn một đỉnh v ngẫu nhiên làm đỉnh ban đầu và chuyển đỉnh v vào cây khung.Bước 2: Thêm tất cả các cạnh nối với v vào danh sách cạnh sẽ xét .Bước 3: Xét các cạnh trong list đến lúc hết:Bước 3.1: kéo ra cạnh gồm trọng số nhỏ tuổi nhất nối trường đoản cú v1 cho một đỉnh v2 chưa nằm trong cây khung. Đưa cạnh này cùng đỉnh v2 vào cây khung.Bước 3.2: Đưa các cạnh nối từ bỏ đỉnh v2 đến những đỉnh chưa bên trong cây khung vào danh sách cạnh sẽ xét.

Ở bước kéo ra cạnh có trọng số bé dại nhất trong những các cạnh vẫn xét, họ sử dụng Min-PriorityQueue để đưa ra cạnh bao gồm trọng số nhỏ tuổi nhất.

2. Định nghĩa API

Để lúc này thuật toán Prim, chúng ta cũng có thể sử dụng kết cấu EdgeWeightedGraph để lưu trữ đồ thị vô hướng có trọng số nhưng mà mình có trình làng qua ở bài viết Tổng quan về thiết bị thị. Bọn họ định nghĩa trừu tượng những 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 edges(); double weight();Class LayzyPrimMST đã 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 dấn vào đồ vật thị vô hướng bao gồm trọng số g và 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 double weight() // to lớn be implemented Lúc này bạn có thể viết hàm main để thử nghiệm với thiết bị 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 ", e.either(), e.other(e.either()), e.weight()); System.out.println("Weight: " + prim.weight());3. Thiết lập thuật toán.Bên vào class LazyPrimMST, bọn họ định nghĩa một vài field cung cấp cho việc tìm và đào bới cây khung bé dại nhất.

private boolean<> marked;private LinkedList mst;private PriorityQueue pq;marked: Mảng boolean lưu lại một đỉnh đang được gửi vào cây form hay chưa.mst: Danh sách những cạnh của cây khung.

Xem thêm: Cách Sửa Lỗi Mic Không Nói Được Win 7, 8, 10, Máy Tính Không Nhận Microphone Win 7

pq: Danh sách những cạnh dùng làm xét sau từng bước chạy thuật toán. Thực hiện PriorityQueue nhằm tiện kéo ra cạnh nhỏ nhất.Thuật toán của họ sẽ chạy trong constructor, ở đây họ sẽ có mang thêm hàm visit(G, v) làm nhiệm vụ ghi lại đỉnh v vẫn được chuyển vào cây khung cùng đư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 như queue vẫn có phần tử:2.1. đem cạnh bé dại nhất trong list đang xét.2.2. Nếu cả hai đỉnh của cạnh này đều phía bên trong cây form thì vứt qua.2.3. Còn không thì đưa cạnh bé dại nhất này vào cây khung.2.4.

Xem thêm: Ý Nghĩa Số 87 Có Ý Nghĩa Gì ? Ý Nghĩa Số 87 Trong Sim Điện Thoại

“Viếng thăm” đỉnh chưa phía bên trong cây khung.

public LazyPrimMST(EdgeWeightedGraph g) pq = new PriorityQueue(Edge::compareTo); marked = new boolean; mst = new LinkedList(); visit(g, 0); while (!pq.isEmpty()) Edge e = pq.poll(); int v = e.either(), w = e.other(v); if (marked && marked) continue; mst.add(e); if (!marked) visit(g, v); if (!marked) visit(g, w); private void visit(EdgeWeightedGraph G, int v) marked = true; for (Edge e : G.adj(v)) if (!marked) pq.add(e); thiết lập các phương thức còn lại của class LazyPrimMST:


Overridepublic 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.0000002-4: 0.6000001-4: 1.0000002-5: 1.5000005-6: 1.9000006-8: 1.7000006-7: 1.8000000-3: 2.100000Weight: 12.6Vẫn đúng với kết quả chạy từng bước một ở nội dung bài viết trước phải không nào!


*

References


THẺ ĐÁNH DẤU prim graph java

Bình luận


Cảm ơn bạn

Your phản hồi has been submitted and will be published once it has been approved. 😊