Related data structure:
Related paradigm:
Related algorithm:
AlgorithmGraphGreedy_AlgorithmMinimum_Spanning_TreeMSTPrim
Prim’s algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted undirected graph. Recall that a MST of a graph is a subset of the edges that connects all the vertices together without any cycles and the minimum possible total edge weight. Different from Kruskal’s with works with edges, algorithm Prim’s algorithm works with vertices and adds a vertex-edge couple to the MST with every iteration.
Implementation
The algorithm starts from an arbitrary vertex as the starting vertex of the MST, and then greedily selects the edge with the minimum weight that connects already selected vertices to a vertex not yet selected for the MST, using the priority queue.
- Starts with an arbitrary vertex and add it to the MST. Initialise a priority queue (often implemented using a min-heap) to store candidate edges (including source vertex and destination vertex) with their weights.
- While there are vertices not yet included in the MST, for the current vertex in the MST, consider all edge incident to it that connect to vertices not yet included in the MST; add these edges into the priority queue.
- We want to extract the edge with minimum weight from the priority queue. If adding this edge to the MST does not form a cycle, add it to the MST and mark the connected vertex as included in the MST.
- Repeat step 2 and 3 until all vertices are included in the MST, or the queue is empty (meaning we encountered a disconnected graph).
- The edges added to the MST during the process form the MST.
This implementation is built upon the adjacency list.
public class GraphAdjList {
private Map<Integer, List<Edge>> adjList;
private int numVertices;
// ...
public void primMST() {
// a min-heap that edge with minimum value placed at the root
PriorityQueue<Edge> minHeap = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));
Set<Integer> visited = new HashSet<>();
Map<Integer, Edge> minEdge = new HashMap<>();
int totalWeight = 0;
// start from an arbitrary vertex (here, we start from vertex 0)
int startVertex = 0;
visited.add(startVertex);
// add all edges adjacent to startVertex to the min heap
for (Edge edge : adjList.get(startVertex)) {
minHeap.offer(edge);
}
// loop until all vertices are visited
while (visited.size() < numVertices) {
// get the edge with the minimum edge
Edge minEdge;
do {
minEdge = minHeap.poll();
} while (minEdge != null && visited.contains(minEdge.dest));
if (minEdge == null) break;
// mark the visited vertex as visited
visited.add(minEdge.dest);
totalWeight ++ minEdge.weight;
// add all edges from the newly visited vertex to the min heap
for (Edge edge : adjList.get(minEdge.dest)) {
if (!visited.contains(edge.dest)) {
minHeap.offer(edge);
}
}
}
}
}Back to parent page: ADT - Graph
Reference: