Prim算法是计算机科学和图论领域中非常流行的一种算法。它主要用于寻找加权无向图的最小生成树。什么是最小生成树呢？它是图的一个子集，能够以最小的总边权连接所有顶点，并且保证不会形成任何环路。在本文中，我们将一起探讨如何使用Java编程语言来实现Prim算法，涵盖添加边、初始化图、设置起始点、构建最小生成树（MST）以及其他必要的操作。
#### Prim算法主要用于做什么？
Prim算法通常用于网络设计领域，例如规划电信网络、电网以及交通运输网络。在这些场景中，我们的目标是以最小的成本或距离将所有节点连接起来。最终，它在各个领域中构建出最优的网络结构。
!<a href="https://media.geeksforgeeks.org/wp-content/uploads/20240530181114/PrimAlgo-768.webp">PrimAlgo
结合示例逐步解析：
> #### 图结构：
>
> 该图包含4个顶点（0, 1, 2, 3）和5条边，其权重如下：
>
>
> – 从顶点 0 到 1 的边，权重为 10。
> – 从顶点 0 到 2 的边，权重为 6。
> – 从顶点 0 到 3 的边，权重为 5。
> – 从顶点 1 到 3 的边，权重为 15。
> – 从顶点 2 到 3 的边，权重为 4。
>
> #### 最小生成树：
>
> 注：虽然原文提及了Kruskal算法，但在讨论Prim算法的上下文中，实际上是在描述如何通过选择权重最小的边来构建MST。 我们可以看到，通过选择权重较小的边，我们可以逐步构建出MST：
>
>
> – 从顶点 2 到 3 的边，权重为 4
> – 从顶点 0 到 3 的边，权重为 5
> – 从顶点 0 到 1 的边，权重为 10
>
> 这些边在未形成环路的情况下连接了所有四个顶点，从而构成了总权重为 19 的最小生成树。
Prim算法的应用场景：
- 设计经济高效的通信网络
- 建设成本最低的电网或管道网络
- 规划道路网络以最大程度降低建设成本
Prim算法的伪代码：
这是一个简单的Prim算法伪代码
function prim(graph):
create a set called MST (minimum spanning tree)
create a priority queue (min-heap) for edges, initialized with a random edge
create a set to keep track of visited nodes
while the priority queue is not empty:
edge = priority_queue.pop()
if edge‘s end node is not in visited nodes:
add edge to MST
add edge‘s end node to visited nodes
for each edge connected to edge‘s end node:
if the other end of the edge is not in visited nodes:
add the edge to the priority queue
return MST
Prim算法的Java实现：
让我们来看看具体的Java代码实现。
Java
// Java Program to Implement Prim‘s Algorithm
import java.util.*;
// Class to represent an edge in the graph
class Edge {
int source;
int dest;
int weight;
// Constructor to initialize an edge
Edge(int source, int dest, int weight) {
this.source = source;
this.dest = dest;
this.weight = weight;
}
}
// Class to represent the graph
class Graph {
int vertices;
LinkedList[] adjacencyList;
// Constructor to initialize the graph with
// the given number of vertices
Graph(int vertices) {
this.vertices = vertices;
adjacencyList = new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adjacencyList[i] = new LinkedList();
}
}
// Method to add an edge to the graph
void addEdge(int source, int dest, int weight) {
Edge edge = new Edge(source, dest, weight);
adjacencyList[source].add(edge);
// Adding the reverse edge since it‘s an undirected graph
adjacencyList[dest].add(new Edge(dest, source, weight));
}
// Method to implement Prim‘s algorithm to
// find the Minimum Spanning Tree (MST)
void primMST() {
// Array to keep track of vertices included in MST
boolean[] inMST = new boolean[vertices];
// Priority queue to select the edge
// with the smallest weight
PriorityQueue priorityQueue =
new PriorityQueue(Comparator.comparingInt(e -> e.weight));
// List to store the MST edges
List mst = new ArrayList();
// Start from any vertex, here it‘s 0
int startVertex = 0;
// Mark the start vertex as included in MST
inMST[startVertex] = true;
// Add all edges from the start vertex to the priority queue
for (Edge edge : adjacencyList[startVertex]) {
priorityQueue.add(edge);
}
// Process the edges in the priority queue
while (!priorityQueue.isEmpty()) {
// // Get the edge with the smallest weight
Edge currentEdge = pri