Prim’s Algorithm in Java: Learn with Practical Examples
Many real-world networks need to connect a set of locations while keeping construction or maintenance costs as low as possible. Whether you’re designing a telecommunications network, laying electrical cables, building roads, or planning water distribution systems, the challenge is often the same: connect everything using the least amount of resources.
In graph theory, this problem can be modeled using a Minimum Spanning Tree (MST). Given a weighted, undirected graph, a Minimum Spanning Tree connects every vertex without creating cycles while minimizing the total weight of the selected edges. In other words, it produces the cheapest possible network that still keeps every vertex connected.
One of the most important algorithms for finding a Minimum Spanning Tree is Prim’s Algorithm. Developed by Czech mathematician Vojtěch Jarník in 1930 and later rediscovered by Robert Prim and Edsger Dijkstra, it remains one of the most widely taught greedy algorithms in computer science.
Prim’s Algorithm builds a Minimum Spanning Tree incrementally. Starting from a single vertex, it repeatedly selects the lowest-cost edge that connects a vertex already in the tree to a vertex outside it. By continuing this process until every vertex has been included, the algorithm constructs an MST with the smallest possible total weight.
Because it grows outward from a starting point, Prim’s Algorithm is particularly well suited to scenarios where a network expands gradually, such as connecting cities, offices, routers, substations, or other facilities. Its simplicity, efficiency, and practical relevance have made it a cornerstone topic in graph theory, algorithms, and software engineering courses.
In this article, we’ll explore how Prim’s Algorithm works, examine the greedy strategy behind it, implement it step by step in Java, discuss the Priority Queue data structure that powers its efficiency, and work through practical examples that demonstrate where and why it is useful.
What Is Prim’s Algorithm? 🔍
Prim’s Algorithm is a greedy algorithm used to find a Minimum Spanning Tree (MST) in a weighted, undirected graph. A spanning tree is a subset of edges that:
- Connects every vertex in the graph
- Contains no cycles
- Uses exactly V − 1 edges (V = number of vertices)
In simple terms, an MST connects every node in the graph while keeping the overall cost as low as possible.
Unlike e.g. Kruskal’s Algorithm, which considers all edges globally and builds the tree by choosing the cheapest edges across the entire graph, Prim’s Algorithm grows a single tree from a chosen starting vertex. At each step, it selects the cheapest edge that connects the existing tree to a new vertex. This makes Prim’s Algorithm feel more like an expanding wave that spreads through the graph one connected region at a time.
The process is straightforward:
- Choose any starting vertex.
- Mark it as part of the MST.
- Find the cheapest edge connecting the MST to an unvisited vertex.
- Add that edge and vertex to the MST.
- Repeat until all vertices are included.
Because the algorithm always chooses the lowest-cost valid connection available at each step, it follows the greedy approach.
A useful way to visualize Prim’s Algorithm is to imagine building a road network from a single city. Starting from one city, we repeatedly build the cheapest road that reaches a city not yet connected to our growing network. Over time, the network expands outward until every city becomes connected. The same idea applies to laying cables between offices, connecting substations in a power grid, or linking routers in a communication backbone.
By always selecting the cheapest expansion, Prim’s Algorithm guarantees a Minimum Spanning Tree with the smallest possible total weight.
When Should You Use Prim’s Algorithm? 🧐
Prim’s Algorithm is designed to solve the Minimum Spanning Tree (MST) problem — selecting a subset of edges that connects all vertices while minimizing total edge weight and avoiding cycles.
It is most useful when your goal is not to find the shortest route between two points, but to connect an entire set of points as cheaply as possible. In other words, Prim’s Algorithm is the right choice when you want to build a network, not navigate through one. Common applications include:
- Road network construction
- Electrical power grid design
- Computer network infrastructure
- Water distribution systems
- Telecommunications backbone networks
- Pipeline and utility planning
- Sensor and communication network layout
In each of these scenarios, the goal is to connect every location while minimizing infrastructure costs. For example, a city planner may want to connect several neighborhoods with the least expensive road system possible. A telecom company may want to connect data centers and offices using the cheapest cable layout. An electrical engineer may want to design a transmission network that reaches every substation without unnecessary wiring.
Prim’s Algorithm is particularly effective when working with dense graphs, where the number of edges is relatively large. Because it expands from one vertex outward and repeatedly chooses the cheapest edge that crosses the boundary of the current tree, it performs very well when many possible connections exist. When implemented with an adjacency list and a Priority Queue, it runs in O(E log V) where:
- V = number of vertices
- E = number of edges
The Priority Queue efficiently selects the next cheapest edge that expands the tree. This makes Prim’s Algorithm a strong choice when the graph is large and the cost of repeatedly scanning all edges would be too high.
The space complexity is O(V + E) because the algorithm stores the graph structure, visited vertices, and Priority Queue contents.
Prim’s Algorithm is often the best option when:
- The graph is connected or can be treated as connected
- You want to grow the MST from a specific starting point
- The graph has many edges
- The graph is stored as an adjacency list
- You need an efficient MST solution for infrastructure-style problems
Prim’s Algorithm is not always the easiest or fastest choice in such situations:
- If your graph is already represented as an edge list, Kruskal’s Algorithm may be simpler.
- If the graph is sparse and edge sorting is convenient, Kruskal’s Algorithm can be a better fit.
- If you need shortest paths instead of a minimum spanning tree, you should use Dijkstra’s, Bellman-Ford, or Floyd-Warshall instead.
So, Prim’s Algorithm is best used when the problem is about connecting everything with minimum total cost, especially when the graph is dense and the network grows naturally from one starting point.
Limitations of Prim’s Algorithm 📉
As already mentioned, although Prim’s Algorithm is highly efficient, it is not the ideal solution for every graph problem.
1. Requires a Connected Graph
Prim’s Algorithm assumes the graph is connected. If the graph contains multiple disconnected components, a single Minimum Spanning Tree cannot be produced. In that case, you would need to run the algorithm separately on each component or use a different approach depending on the problem.
2. Priority Queue Overhead
Efficient implementations rely on a Priority Queue (Min Heap). While highly effective, maintaining the heap introduces additional complexity compared to simpler graph traversals. This overhead is worth it for large graphs, but it may be unnecessary for very small inputs.
3. Less Natural for Edge-Based Data
Prim’s Algorithm performs best when graphs are represented using adjacency lists. If data is already stored as an edge list, Kruskal’s Algorithm is often simpler to implement because it works directly with edges and sorting.
4. Does Not Solve Shortest-Path Problems
A Minimum Spanning Tree minimizes the total weight of the entire network, not the shortest distance between specific vertices. For example:
- Dijkstra’s Algorithm finds shortest paths from a source vertex.
- Bellman-Ford Algorithm supports negative weights.
- Floyd-Warshall Algorithm computes all-pairs shortest paths.
- Prim’s Algorithm constructs a Minimum Spanning Tree.
Using Prim’s Algorithm when shortest paths are required can produce incorrect solutions.
5. The Starting Vertex Can Affect Build Order
Prim’s Algorithm can start from any vertex in a connected graph, and the total MST weight will remain the same. However, the order in which vertices and edges are added may differ depending on the starting point. This matters in implementations where you want to trace the algorithm step by step or visualize how the tree grows.
Get Robin Viktorsson’s stories in your inbox
Join Medium for free to get updates from this writer.
Despite these limitations, Prim’s Algorithm remains one of the most efficient and practical MST algorithms available.
From Theory to Practice 🛠️
Unlike Kruskal’s Algorithm, which focuses on sorting edges, Prim’s Algorithm grows a tree vertex by vertex.
Because the algorithm repeatedly examines neighboring vertices, an adjacency list is usually the most natural graph representation. This is especially true in real-world systems where each location or device is connected only to a limited set of nearby or relevant neighbors. The algorithm maintains:182368
- A set of visited vertices
- A Priority Queue containing candidate edges
- The growing Minimum Spanning Tree
At each step, the cheapest edge leaving the current tree is selected and added to the MST. This makes Prim’s Algorithm particularly useful in applications where the network expands outward from a central point or where the cheapest next connection must always be chosen from the current frontier.
1. Prim’s Algorithm Implementation
Before looking at the code, it helps to understand what this implementation 182368is doing. The Java example below uses an adjacency list to represent the graph, a PriorityQueue to always select the cheapest available edge, and a visited array to ensure each vertex is added to the Minimum Spanning Tree only once.
Starting from vertex 0, the algorithm gradually builds the Minimum Spanning Tree. At each step, it selects the lowest-weight edge that connects a vertex already in the tree to a vertex that has not yet been visited. This greedy strategy ensures the tree stays connected while keeping the total weight minimal.
import java.util.*;
// Represents a weighted edge in the graph
class Edge {
int destination; // The node this edge points to
int weight; // Cost of traveling this edge
Edge(int destination, int weight) {
this.destination = destination;
this.weight = weight;
}
}
public class Main {
// Prim's Algorithm implementation to compute MST
public static void prim(List<List<Edge>> graph, int vertices) {
// Tracks whether a vertex is already included in the MST
boolean[] visited = new boolean[vertices];
// Min-heap priority queue:
// stores {vertex, edgeWeight}, always extracts smallest weight first
PriorityQueue<int[]> pq =
new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
// Start MST from vertex 0 with cost 0
pq.offer(new int[]{0, 0});
int totalWeight = 0; // Accumulates total cost of MST edges
System.out.println("Minimum Spanning Tree:");
// Continue until all reachable vertices are processed
while (!pq.isEmpty()) {
// Extract the edge with the smallest weight
int[] current = pq.poll();
int vertex = current[0]; // current node
int weight = current[1]; // cost to reach it
// Skip if already included in MST (prevents cycles)
if (visited[vertex]) {
continue;
}
// Mark this vertex as part of MST
visited[vertex] = true;
// Add its connection cost to total MST weight
totalWeight += weight;
// Print step-by-step MST construction
System.out.println("Vertex " + vertex +
" added with edge weight " + weight);
// Explore all adjacent edges of current vertex
for (Edge edge : graph.get(vertex)) {
// Only consider edges leading to unvisited vertices
if (!visited[edge.destination]) {
// Add candidate edge to priority queue
pq.offer(new int[]{
edge.destination,
edge.weight
});
}
}
}
// Final MST cost output
System.out.println("Total Weight: " + totalWeight);
}
public static void main(String[] args) {
int vertices = 4; // Number of nodes in the graph
// Adjacency list representation of the graph
List<List<Edge>> graph = new ArrayList<>();
// Initialize adjacency list for each vertex
for (int i = 0; i < vertices; i++) {
graph.add(new ArrayList<>());
}
// Add undirected weighted edges (bidirectional connections)
graph.get(0).add(new Edge(1, 10)); // Edge 0 -> 1
graph.get(1).add(new Edge(0, 10)); // Edge 1 -> 0
graph.get(0).add(new Edge(2, 6)); // Edge 0 -> 2
graph.get(2).add(new Edge(0, 6)); // Edge 2 -> 0
graph.get(0).add(new Edge(3, 5)); // Edge 0 -> 3
graph.get(3).add(new Edge(0, 5)); // Edge 3 -> 0
graph.get(1).add(new Edge(3, 15)); // Edge 1 -> 3
graph.get(3).add(new Edge(1, 15)); // Edge 3 -> 1
graph.get(2).add(new Edge(3, 4)); // Edge 2 -> 3 (cheapest link)
graph.get(3).add(new Edge(2, 4)); // Edge 3 -> 2
// Run Prim's algorithm to compute MST
prim(graph, vertices);
}
}
// Output:
// Minimum Spanning Tree:
// Vertex 0 added with edge weight 0
// Vertex 3 added with edge weight 5
// Vertex 2 added with edge weight 4
// Vertex 1 added with edge weight 10
// Total Weight: 19The implementation begins by initializing a visited array to track which vertices have already been included in the MST. A PriorityQueue (used as a min-heap) ensures that the smallest available edge is always processed first.
The algorithm starts at vertex 0, pushing it into the queue with weight 0. In each iteration, it extracts the cheapest candidate edge. If the target vertex is already visited, it is skipped. Otherwise, the vertex is added to the MST, its weight contributes to the total cost, and all outgoing edges to unvisited vertices are pushed into the queue.
Because the priority queue continuously maintains candidate edges sorted by weight, the algorithm never needs to scan the entire graph to find the next best choice. It simply expands the tree step by step until all vertices are included, producing a Minimum Spanning Tree with minimum total weight.
2. Representing Graphs with Adjacency Lists
Because Prim’s Algorithm frequently examines neighboring vertices, adjacency lists provide efficient access to outgoing edges. Each vertex stores a list of adjacent vertices and the corresponding edge weights.
This allows the algorithm to quickly discover candidate edges while expanding the tree. In practical terms, this is useful when each node only connects to a small number of nearby nodes, such as cities connected by roads or routers connected by network links.
3. Understanding the Priority Queue
The Priority Queue is the heart of Prim’s Algorithm. At any moment, the queue contains all edges that could potentially expand the current tree. Whenever a new vertex is added:
- Its outgoing edges are inserted into the queue.
- The cheapest edge is extracted.
- If it leads to an unvisited vertex, it becomes part of the MST.
This ensures the algorithm always selects the lowest-cost expansion available. In real-world use, this means Prim’s Algorithm is constantly evaluating the cheapest next step in building a network. That is why it works so well for infrastructure planning and other cost-sensitive connection problems.
4. Growing the Minimum Spanning Tree
Unlike Kruskal’s Algorithm, which merges disconnected components, Prim’s Algorithm maintains a single connected tree throughout execution.
The MST grows outward one vertex at a time until every vertex becomes part of the tree. This growth pattern is especially useful when the network naturally expands from a central hub. For example, a company may begin with one headquarters and gradually connect branch offices, or a utility provider may extend service from one substation to surrounding areas.
5. Why Priority Queues Improve Performance
Without a Priority Queue, the algorithm would repeatedly scan all available edges to find the cheapest candidate. A Min Heap allows this operation to be performed efficiently, reducing the overall running time to O(E log V).
This efficiency is one of the main reasons Prim’s Algorithm is widely used in practice. It allows large graphs to be processed without checking every possible edge at every step.
6. Object-Oriented Implementation
For simplicity, the earlier implementation keeps everything inside a single class. This is useful for learning because it shows all components of the algorithm in one place without unnecessary abstraction.
In real-world applications, however, a more object-oriented design is preferred. The graph structure and the algorithm logic are usually separated into different classes. A Graph class is responsible for storing vertices and edges, while a PrimMST class handles the Minimum Spanning Tree construction.
This separation improves readability, makes the code easier to maintain, and allows the algorithm to be reused in different contexts such as network simulation, graph visualization, infrastructure planning, or performance analysis.
import java.util.*;
// Represents an edge in the graph
class Edge {
int destination;
int weight;
Edge(int destination, int weight) {
this.destination = destination;
this.weight = weight;
}
}
// Graph class responsible for storing vertices and edges
class Graph {
int vertices;
List<List<Edge>> adjacencyList;
Graph(int vertices) {
this.vertices = vertices;
this.adjacencyList = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
adjacencyList.add(new ArrayList<>());
}
}
// Add an undirected weighted edge
void addEdge(int source, int destination, int weight) {
adjacencyList.get(source)
.add(new Edge(destination, weight));
adjacencyList.get(destination)
.add(new Edge(source, weight));
}
}
// Prim's Algorithm implementation class
class PrimMST {
void runPrim(Graph graph) {
boolean[] visited =
new boolean[graph.vertices];
PriorityQueue<int[]> pq =
new PriorityQueue<>(
Comparator.comparingInt(a -> a[1])
);
// Start from vertex 0
pq.offer(new int[]{0, 0});
int totalWeight = 0;
System.out.println("Minimum Spanning Tree:");
while (!pq.isEmpty()) {
int[] current = pq.poll();
int vertex = current[0];
int weight = current[1];
if (visited[vertex]) {
continue;
}
visited[vertex] = true;
totalWeight += weight;
System.out.println(
"Vertex " + vertex +
" added with edge weight " +
weight
);
for (Edge edge :
graph.adjacencyList.get(vertex)) {
if (!visited[edge.destination]) {
pq.offer(
new int[]{
edge.destination,
edge.weight
}
);
}
}
}
System.out.println(
"Total Weight: " + totalWeight
);
}
}
// Main class to run the program
public class Main {
public static void main(String[] args) {
// Create graph with 4 vertices
Graph graph = new Graph(4);
// Add weighted edges
graph.addEdge(0, 1, 10);
graph.addEdge(0, 2, 6);
graph.addEdge(0, 3, 5);
graph.addEdge(1, 3, 15);
graph.addEdge(2, 3, 4);
// Run Prim's Algorithm
new PrimMST().runPrim(graph);
}
}
// Output:
// Minimum Spanning Tree:
// Vertex 0 added with edge weight 0
// Vertex 3 added with edge weight 5
// Vertex 2 added with edge weight 4
// Vertex 1 added with edge weight 10
// Total Weight: 19This object-oriented version separates concerns clearly. The Graph class is responsible only for storing the graph structure, while the PrimMST class focuses entirely on the algorithm itself. This makes the code easier to extend and maintain as applications grow larger.
Despite the structural change, the algorithm remains exactly the same. A Priority Queue is used to repeatedly select the cheapest edge that expands the current tree, and vertices are marked as visited to ensure that cycles are never introduced. The process continues until all vertices have been added to the Minimum Spanning Tree.
Practical Examples 💡
Prim’s Algorithm is widely used whenever a network needs to be expanded from an existing starting point while keeping total costs as low as possible. Because the algorithm grows outward one vertex at a time, it naturally fits many real-world infrastructure and optimization problems. Below are three practical examples that demonstrate how it can be applied.
1. Procedural Dungeon Generation in Games
Prim’s Algorithm is commonly used in procedural content generation, particularly for creating dungeon layouts in games. Rooms can be represented as vertices, while possible corridors between rooms become weighted edges.
The goal is to connect every room while avoiding unnecessary loops and minimizing the total number of corridors. This produces a dungeon that is fully explorable while remaining efficient and easy to navigate.
Many roguelikes, puzzle games, and adventure games use Minimum Spanning Trees as a foundation for generating maps before optionally adding a few extra connections to create alternative routes.
// Create a graph representing rooms in a dungeon
Graph graph = new Graph(6);
// Weight = corridor construction cost or distance
// between rooms
graph.addEdge(0, 1, 4); // Corridor between Room 0 and Room 1
graph.addEdge(0, 2, 3); // Short corridor
graph.addEdge(1, 2, 1); // Cheapest connection
graph.addEdge(1, 3, 5); // Longer hallway
graph.addEdge(2, 4, 6); // Distant room connection
graph.addEdge(3, 4, 2); // Efficient route
graph.addEdge(3, 5, 7); // Boss room path
graph.addEdge(4, 5, 3); // Alternative route
// Generate the dungeon backbone
new PrimMST().runPrim(graph);
// Output:
// Minimum Spanning Tree:
// Vertex 0 added with edge weight 0
// Vertex 2 added with edge weight 3
// Vertex 1 added with edge weight 1
// Vertex 3 added with edge weight 5
// Vertex 4 added with edge weight 2
// Vertex 5 added with edge weight 3
// Total Weight: 14The resulting Minimum Spanning Tree creates a dungeon where every room can be reached while using the minimum number of corridors necessary to maintain connectivity. Game developers often start with this structure and then add a few extra corridors afterward to create loops, shortcuts, and alternative exploration paths.
2. Water Distribution Network
One common application of Prim’s Algorithm is designing a water distribution system. Reservoirs, pumping stations, and distribution hubs can be represented as vertices, while possible pipeline connections become weighted edges. The weight of each edge represents the cost of installing and maintaining a pipeline.
Rather than building every possible connection, engineers want to connect all locations using the minimum amount of pipe and construction cost. Prim’s Algorithm helps identify the cheapest network that still delivers water to every location.
// Create a graph representing water facilities
Graph graph = new Graph(5);
// Each edge represents a possible pipeline
// Weight = installation cost of the pipeline
graph.addEdge(0, 1, 3); // Low-cost pipeline
graph.addEdge(0, 2, 8); // Long-distance connection
graph.addEdge(1, 2, 2); // Cheapest connection
graph.addEdge(1, 3, 5); // Medium-cost pipeline
graph.addEdge(2, 4, 7); // Expensive route
graph.addEdge(3, 4, 4); // Alternative connection
// Build the cheapest water distribution network
new PrimMST().runPrim(graph);
// Output:
// Minimum Spanning Tree:
// Vertex 0 added with edge weight 0
// Vertex 1 added with edge weight 3
// Vertex 2 added with edge weight 2
// Vertex 3 added with edge weight 5
// Vertex 4 added with edge weight 4
// Total Weight: 14The resulting Minimum Spanning Tree connects every facility while minimizing total pipeline construction cost.
3. Wireless Sensor Network Deployment
Wireless sensor networks are commonly used in agriculture, environmental monitoring, smart cities, and industrial automation. Each sensor can be modeled as a vertex, while possible communication links between sensors become weighted edges.
The weight of each edge may represent installation cost, signal loss, power consumption, or communication expense. Prim’s Algorithm can determine the most efficient communication backbone connecting all sensors.
// Create a graph representing wireless sensors
Graph graph = new Graph(6);
// Weight = communication or installation cost
graph.addEdge(0, 1, 1); // Nearby sensors
graph.addEdge(0, 2, 4); // Longer communication link
graph.addEdge(1, 2, 2); // Efficient connection
graph.addEdge(1, 3, 5); // Medium-cost link
graph.addEdge(2, 4, 3); // Good connection
graph.addEdge(3, 5, 4); // Sensor expansion
graph.addEdge(4, 5, 2); // Low-cost communication path
// Build the minimum-cost sensor network
new PrimMST().runPrim(graph);
// Output:
// Minimum Spanning Tree:
// Vertex 0 added with edge weight 0
// Vertex 1 added with edge weight 1
// Vertex 2 added with edge weight 2
// Vertex 4 added with edge weight 3
// Vertex 5 added with edge weight 2
// Vertex 3 added with edge weight 4
// Total Weight: 12This produces a communication structure that connects all sensors while minimizing deployment and operating costs.
Prim’s Algorithm is one of the most elegant examples of a greedy graph algorithm. By starting from a single vertex and repeatedly selecting the cheapest edge that expands the current tree, it efficiently constructs a Minimum Spanning Tree with the lowest possible total weight.
Its combination of simplicity, efficiency, and practical relevance makes it a cornerstone topic in graph theory and software engineering. When paired with an adjacency list and Priority Queue, Prim’s Algorithm performs exceptionally well, particularly on dense graphs where many connections exist between vertices.
Like Kruskal’s Algorithm, Prim’s Algorithm is not designed for shortest-path problems. Its purpose is to minimize the total cost of an entire network rather than optimize routes between individual vertices.
From road systems and telecommunications to electrical grids and infrastructure planning, Prim’s Algorithm demonstrates how a simple greedy strategy can solve complex optimization problems efficiently. More than ninety years after its original discovery, it remains one of the most important and widely used algorithms in computer science.
Conclusion 📣
Prim’s Algorithm is a powerful and practical greedy approach for solving the Minimum Spanning Tree problem, enabling efficient design of cost-optimized networks in both theoretical and real-world settings. By incrementally expanding from a starting vertex and always selecting the lowest-cost edge that connects the growing tree to a new vertex, it guarantees a globally optimal solution for connecting all nodes without cycles while minimizing total edge weight.
Through its Java implementations and practical examples, it becomes clear that Prim’s Algorithm is not just an abstract graph theory concept, but a highly applicable tool in areas such as infrastructure planning, telecommunications, water distribution systems, and procedural game content generation. Its reliance on adjacency lists and priority queues allows it to scale effectively to large and dense graphs, making it suitable for real-world engineering problems where efficiency matters.
While it has some limitations — such as requiring a connected graph and not being suited for shortest-path problems — its strengths in building minimal-cost connected networks make it a foundational algorithm in computer science. Understanding Prim’s Algorithm not only deepens one’s grasp of greedy strategies and graph theory but also provides a practical method for solving a wide range of optimization challenges in software engineering and system design.
Thanks for reading! Please give this article a clap and follow me if you enjoyed it 😃
