CÀI ĐẶT THUẬT TOÁN PRIM C++

     

Bài viết Thuật toán Prim: tìm cây khung bé dại nhất đã trình làng đến các bạn ý tưởng của thuật toán này tương tự như từng bước chạy thuật toán. Tiếp theo sẽ là phần hướng dẫn setup thuật toán Prim mang lại đồ thị vô hướng bao gồm trọng số bằng ngôn từ 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 phát minh cơ phiên bản của thuật toán Prim:

Bước 1: lựa chọn 1 đỉnh v bất kỳ làm đỉnh bước đầu và đưa đỉ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 đang xét .Bước 3: Xét những cạnh trong danh sách đến lúc hết:Bước 3.1: kéo ra cạnh tất cả trọng số bé dại nhất nối từ bỏ v1 mang đến một đỉnh v2 chưa nằm trong cây khung. Đưa cạnh này và đỉnh v2 vào cây khung.Bước 3.2: Đưa những cạnh nối từ bỏ đỉnh v2 đến các đỉnh chưa bên trong cây khung vào danh sách cạnh sẽ xét.

Ở bước lôi ra cạnh có trọng số nhỏ tuổi nhất trong số các cạnh sẽ xét, họ sử dụng Min-PriorityQueue để mang ra cạnh có trọng số bé dại nhất.

2. Định nghĩa API

Để hiện thực thuật toán Prim, bạn cũng có thể sử dụng cấu trúc EdgeWeightedGraph để tàng trữ đồ thị vô hướng bao gồm trọng số mà lại mình có giới thiệu qua ở nội dung bài viết Tổng quan liêu về thiết bị thị. Họ định nghĩa trừu tượng các phương thức của một class làm trọng trách tìm cây form như sau:

public interface PrimMST Iterable edges(); double weight();Class LayzyPrimMST đã làm trọng trách tìm cây khung nhỏ nhất mang lại đồ thị g với những phương thức:

LazyPrimMST(EdgeWeightedGraph g): Constructor dìm vào đồ gia dụng thị vô hướng bao gồm trọng số g và thực hiện tìm cây khung nhỏ dại nhất.edges(): Trả về các cạnh của cây khung nhỏ dại nhất.weight(): Trả về trọng số của cây khung nhỏ tuổi nhất.

public class LazyPrimMST implements PrimMST { public LazyPrimMST(EdgeWeightedGraph g) // lớn be implemented
Override public double weight() // lớn be implemented Lúc này bạn cũng có thể viết hàm main để kiểm tra với đồ vật thị $G$ trong nội dung 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 trong class LazyPrimMST, chúng ta định nghĩa một số trong những field cung cấp cho việc tìm kiếm cây khung nhỏ nhất.

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

Xem thêm: Cách Làm Túi Quà Bằng Giấy Handmade Đơn Giản, Nhanh Chóng, Cách Làm Túi Giấy Đựng Quà Handmade Trong 2 Phút

pq: Danh sách các cạnh dùng để xét sau từng bước một chạy thuật toán. Thực hiện PriorityQueue nhằm tiện lấy ra cạnh nhỏ tuổi nhất.Thuật toán của chúng ta sẽ chạy vào constructor, nghỉ ngơi đây bọn họ sẽ khái niệm thêm hàm visit(G, v) có tác dụng nhiệm vụ đánh dấu đỉnh v vẫn được gửi vào cây khung và đưa những cạnh kề vào PriorityQueue.

Các cách thực hiện:

1. “Viếng thăm” đỉnh $0$.2. Xét nếu như queue vẫn đang còn phần tử:2.1. rước cạnh nhỏ nhất trong danh sách đang xét.2.2. Nếu cả hai đỉnh của cạnh này đều bên trong cây khung thì vứt qua.2.3. Còn không thì đưa cạnh nhỏ dại nhất này vào cây khung.2.4.

Xem thêm: Đầy Tháng Cho Bé Gái Tính Như Thế Nào, Cúng Đầy Tháng Cho Bé Như Thế Nào

“Viếng thăm” đỉnh chưa phía 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); setup các phương thức còn sót lại của class LazyPrimMST:


Overridepublic double weight() return mst.stream().mapToDouble(Edge::weight).sum();Sau khi trả tất, cùng chạy thử lại hàm main để thấy 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 mỗi bước ở nội dung bài viết trước đề nghị 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 & will be published once it has been approved. 😊