Greedy Optimization and Prim’s Minimum Spanning Tree Algorithm

Verified Sources

Sep 11, 2026

Learning objectives

By the end of this section, you should be able to:

Define an optimal solution.
Explain the greedy approach and its purpose.
Distinguish local optimality from global optimality.
Describe the greedy-choice property and optimal substructure.
Explain why Prim’s algorithm is greedy.
Construct a minimum spanning tree manually using Prim’s algorithm.
Analyze the correctness and time complexity of Prim’s algorithm.

A greedy algorithm constructs a solution incrementally. At every stage, it selects the choice that appears most beneficial immediately and does not normally revise earlier decisions. Greedy algorithms are attractive because they are often simple and efficient, but they produce a globally optimal result only for problems with suitable structural properties.

Greedy algorithm - Wikipedia - Definition of greedy algorithms and examples including Prim’s algorithm. ↩
Greedy Algorithms: Definition & Examples - Greedy-choice property and optimal substructure. ↩

Prim’s Algorithm in 2 Minutes

1. What is an optimal solution?

An optimization problem consists of:

A set of feasible solutions.
An objective function.
A goal to maximize or minimize that function.

If $S$ is a feasible solution and $f(S)$ is its objective value, then:

For a minimization problem, an optimal solution $S^*$ satisfies
$f(S^*) \leq f(S)$
for every feasible solution $S$ .
For a maximization problem, an optimal solution $S^*$ satisfies
$f(S^*) \geq f(S)$
for every feasible solution $S$ .

For a weighted graph, a minimum spanning tree is an optimal solution to the problem of connecting every vertex with minimum total cost.

A spanning tree of a connected graph $G=(V,E)$ must:

Include every vertex in $V$ .
Contain exactly $|V|-1$ edges.
Be connected.
Contain no cycle.

If $T$ is a spanning tree, its weight is:

w(T)=\sum_{e\in T}w(e)

The objective of the minimum spanning tree problem is:

\min_{T\text{ is a spanning tree}} w(T)

Prim’s Algorithm – Explained with a Pseudocode Example - Definition and purpose of a minimum spanning tree. ↩

Local versus global optimality

A locally optimal choice is best at the current step. A globally optimal solution is best over the entire feasible solution space. A greedy algorithm is correct only when its local choices can be proven to lead to a global optimum.

2. What does “optimal solution in the greedy approach” mean?

In a greedy approach, an optimal solution is obtained by repeatedly making locally optimal choices that can be shown to preserve the possibility of reaching a globally optimal solution.

The phrase does not mean that every locally cheapest choice is automatically correct. Instead, it means that the problem has a mathematical property allowing the local choice to be safely committed.

For Prim’s algorithm, the local choice is:

Select the minimum-weight edge crossing from the vertices already in the partial tree to a vertex outside it.

This edge is safe because of the cut property of minimum spanning trees.

If a cut divides the vertices into two sets $S$ and $V-S$ , then a minimum-weight edge crossing that cut is called a light edge. At least one MST contains that light edge. Therefore, Prim’s locally minimum edge can be included without destroying optimality.

The Cut Property - Educational explanation of the cut property used to justify MST choices. ↩

3. Properties of the greedy approach

3.1 Greedy-choice property

The greedy-choice property states that an optimal solution can be obtained by making a locally best choice first and then solving the remaining problem.

For Prim’s algorithm:

The current tree defines a cut.
The lightest edge crossing that cut is selected.
That edge is safe to add to an MST.

The algorithm does not need to examine all possible future trees before making the choice.

3.2 Optimal substructure

The optimal substructure property means that after making a correct choice, the remaining portion of the problem can be solved optimally.

For an MST, if an edge is safely added to the growing tree, the remaining task is to connect the unvisited vertices with minimum additional cost.

3.3 Feasibility preservation

A greedy choice must preserve feasibility. In Prim’s algorithm, a selected edge:

Connects the current tree to a new vertex.
Does not create a cycle.
Maintains connectivity of the partial solution.

3.4 Irrevocable decisions

Greedy algorithms generally do not reconsider choices. Once Prim’s algorithm adds an edge to the MST, that edge remains in the final tree.

3.5 Incremental construction

The solution is built one component at a time. Prim’s algorithm starts with one vertex and grows a single connected tree until all vertices are included.

3.6 Objective-directed selection

A selection function determines which candidate is selected. For Prim’s algorithm, the selection function chooses the smallest edge crossing the current tree boundary.

3.7 Proof requirement

A greedy algorithm should be accompanied by a correctness argument. Common proof techniques include:

Exchange arguments.
Cut and cycle properties.
Induction over the number of selected elements.
Staying-ahead arguments.

4. Function of the greedy approach

The function of a greedy approach is to reduce a large optimization problem to a sequence of smaller decisions.

A general greedy algorithm has the following conceptual structure:

A greedy method usually contains these components:

Component	Function
Candidate set	Stores choices that may be added
Selection function	Chooses the locally best candidate
Feasibility test	Checks whether the choice remains valid
Objective function	Measures solution quality
Solution test	Determines whether the construction is complete

For a minimum spanning tree:

Candidate set: Edges adjacent to the current tree.
Selection function: Minimum edge weight.
Feasibility test: The edge must connect to an unvisited vertex.
Objective: Minimize total edge weight.
Solution test: All vertices have been included.

How to determine whether a greedy method is appropriate

1
Step 1
Specify whether the problem seeks to minimize or maximize a measurable objective such as total cost, total weight, time, or number of resources.
2
Step 2
Identify the constraints that every valid solution must satisfy.
3
Step 3
Choose the candidate that appears best according to the current objective.
4
Step 4
Prove that at least one globally optimal solution contains the proposed local choice.
5
Step 5
Show that after the choice is made, the remaining problem has the same optimization structure.
6
Step 6
Use an exchange argument, induction, or a structural theorem such as the MST cut property.
7
Step 7
Determine the time and space required by the selection, feasibility, and update operations.

Greedy approach: common questions

5. Minimum spanning trees

Let $G=(V,E)$ be a connected, undirected, weighted graph. A minimum spanning tree $T$ is a subgraph satisfying:

T\subseteq G

and:

|E(T)|=|V|-1

with minimum total weight:

w(T)=\sum_{e\in E(T)}w(e)

An MST is useful in:

Network and cable design.
Road and pipeline planning.
Electrical distribution.
Cluster analysis.
Broadcast and communication networks.

Prim’s and Kruskal’s algorithms are both greedy MST algorithms, but they grow the solution differently:

Feature	Prim’s algorithm	Kruskal’s algorithm
Growth pattern	Expands one connected tree	Merges separate components
Main choice	Cheapest edge leaving current tree	Cheapest edge in the entire remaining graph
Cycle handling	Selects an outside vertex	Uses disjoint-set detection
Typical data structure	Priority queue	Sorting plus union-find
Best viewpoint	Vertex expansion	Edge selection

6. Prim’s algorithm

Prim’s algorithm begins with an arbitrary vertex and repeatedly adds the least-weight edge connecting the current tree to an unvisited vertex.

Let:

$S$ be the set of vertices already in the tree.
$V-S$ be the unvisited vertices.
$\delta(S)$ be the set of edges with one endpoint in $S$ and the other in $V-S$ .

At each iteration, Prim selects:

e^*=\arg\min_{e\in\delta(S)}w(e)

Then it adds $e^*$ and its outside endpoint to the growing tree.

Invariant

After every iteration:

The selected edges form a tree that is contained in at least one MST.

This invariant is preserved by the cut property.

Prim’s algorithm - Wikipedia - Algorithm description, pseudocode, and implementation variants. ↩

Prim’s algorithm: manual procedure

1
Step 1
Select any vertex as the root. Mark it as visited and place it in the current tree.
2
Step 2
Write down every edge with exactly one endpoint in the current tree.
3
Step 3
Select the boundary edge with minimum weight. If tied, any tied edge may be selected.
4
Step 4
The selected edge must lead to an unvisited vertex. Ignore an edge whose endpoints are both already in the tree.
5
Step 5
Add the selected edge to the MST and mark its previously unvisited endpoint as visited.
6
Step 6
Add edges incident to the newly visited vertex and remove obsolete internal edges.
7
Step 7
When every vertex is included, the selected edges form the MST.

7. Applying Prim’s algorithm to the supplied graph

The supplied image is referenced as:

The edge labels in the image should be read carefully before executing the algorithm. Since the graph image is externally hosted and its labels may not be available as machine-readable text in every rendering environment, the exact numerical MST depends on the visible vertex names and edge weights.

The correct procedure is therefore:

Select the stated starting vertex.
Record all edges incident to it.
Choose the smallest incident edge.
Add the newly reached vertex.
Recompute the minimum edge crossing the current-tree boundary.
Continue until every vertex is included.
Add exactly $|V|-1$ edges.
Sum the selected weights.

Use the following worksheet to transcribe the graph accurately:

Iteration	Current vertices $S$	Candidate crossing edges	Selected edge	Weight	Total
0	Starting vertex	All incident edges	—	—	$0$
1	$S_1$	Edges from $S_1$ to $V-S_1$	$e_1$	$w_1$	$w_1$
2	$S_2$	Edges from $S_2$ to $V-S_2$	$e_2$	$w_2$	$w_1+w_2$
3	$S_3$	Edges from $S_3$ to $V-S_3$	$e_3$	$w_3$	$w_1+w_2+w_3$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
$	V	-1$	$V$	None	$e_{

The final answer must have:

|V|-1

selected edges, no cycle, all vertices connected, and the smallest possible total weight.

Important when reading the supplied graph

Do not choose the globally smallest unused edge unless it crosses from the current tree to an unvisited vertex. Prim’s algorithm is boundary-based; selecting an internal edge can create a cycle or violate the algorithm’s rule.

8. Worked Prim trace format

Suppose the graph has vertices $A,B,C,D,E$ and the selected edges, after reading the graph labels, are determined as follows. The trace should be presented in this form:

Step	Visited set	Boundary edge weights	Greedy choice	MST weight
0	$\{A\}$	$AB:a,\ AC:b,\ AD:c$	Minimum of $a,b,c$	$0$
1	$\{A,\ldots\}$	Newly exposed boundary edges	Lightest valid edge	Previous total $+$ selected weight
2	$\{\ldots\}$	Updated boundary	Lightest valid edge	Previous total $+$ selected weight
3	$\{\ldots\}$	Updated boundary	Lightest valid edge	Previous total $+$ selected weight
4	$V$	None	Stop	Final MST weight

For an actual numerical solution, replace each symbolic weight with the number printed beside the corresponding edge in the supplied image.

A compact final presentation should be:

\operatorname{MST}(G)=\{e_1,e_2,\ldots,e_{|V|-1}\}

and:

w(\operatorname{MST})=\sum_{i=1}^{|V|-1}w(e_i)

9. Correctness proof for Prim’s algorithm

We prove correctness using the cut property.

Claim

At every iteration, the edge selected by Prim’s algorithm is safe and can belong to an MST.

Proof

Assume the current selected vertices are $S$ and the current tree is contained in some MST $T$ . Prim chooses the minimum-weight edge $e$ crossing the cut $(S,V-S)$ .

If $e$ already belongs to $T$ , the claim is immediate.

Otherwise, add $e$ to $T$ . This creates a cycle because $T$ was a tree. The cycle must contain another edge $f$ crossing the same cut. Since $e$ is the lightest edge crossing the cut:

w(e)\leq w(f)

Remove $f$ from the cycle. The result is another spanning tree:

T' = T+e-f

Its weight satisfies:

w(T')=w(T)+w(e)-w(f)\leq w(T)

Because $T$ was already minimum, $T'$ is also an MST. Thus, there exists an MST containing $e$ .

Therefore, every edge selected by Prim is safe. After $|V|-1$ safe edges have been selected, the result is an MST. $\square$

Typical time complexity of Prim’s algorithm

Complexity depends on the graph representation and priority-queue implementation.

10. Complexity analysis

The complexity depends on the representation.

Implementation	Time complexity	Space complexity
Adjacency matrix with linear minimum search	$O(	V
Binary heap and adjacency list	$O((	V
Fibonacci heap and adjacency list	$O(	E

For a connected graph, $|E|\geq |V|-1$ , so binary-heap implementations are often written as:

O(|E|\log |V|)

The adjacency-matrix version can be competitive for dense graphs, where:

|E|\approx |V|^2

The binary-heap version is usually preferable for sparse graphs.

Prim’s Minimum Spanning Tree Algorithm - Complexity comparison for matrix, adjacency-list, and priority-queue implementations. ↩

PRIM(G, start):
    for each vertex v in V:
        key[v] = infinity
        parent[v] = NIL
        inMST[v] = false

    key[start] = 0
    Q = priority queue containing all vertices by key

    while Q is not empty:
        u = EXTRACT-MIN(Q)

        if inMST[u] == true:
            continue

        inMST[u] = true

        for each edge (u, v) with weight w:
            if inMST[v] == false and w < key[v]:
                parent[v] = u
                key[v] = w
                DECREASE-KEY(Q, v, key[v])

    return {(parent[v], v) : v != start}

11. Common mistakes

Choosing the smallest edge in the entire graph
Prim chooses the smallest edge crossing the current cut, not necessarily the globally smallest unused edge.
Adding an edge between two visited vertices
Such an edge is internal to the current tree and creates a cycle.
Stopping too early
A spanning tree requires every vertex. The algorithm stops after $|V|-1$ selected edges.
Forgetting that the graph must be connected
If the graph is disconnected, no single spanning tree exists. Prim instead produces a minimum spanning forest for the reachable component.
Adding more than $|V|-1$ edges
More than $|V|-1$ edges in a connected structure necessarily creates a cycle.
Assuming the MST is always unique
Equal-weight edges can produce multiple valid MSTs with the same total weight.

Exam technique

After every Prim iteration, write the visited set and list only edges that leave it. This makes the cut explicit and prevents accidental selection of an internal edge.

Greedy algorithms and Prim’s algorithm

1 / 8

Question · Term

What is an optimal solution?

Click to reveal

Answer · Definition

A feasible solution with the best objective value among all feasible solutions.

Knowledge Check

Question 1 of 5

Q1Single choice

What is meant by an optimal solution in a minimization problem?

The first feasible solution found

The feasible solution with the smallest objective value

The solution with the largest number of decisions

The solution that uses the most resources

Explore Related Topics

Negative Weight Cycle and the Bellman-Ford Algorithm for Single-Source Shortest Distance

Negative weight cycles are cycles whose total edge weight is negative, and the Bellman‑Ford algorithm computes single‑source shortest distances while detecting such cycles.

A reachable negative weight cycle makes the shortest‑distance problem undefined because repeated traversal can lower the path cost without bound.
Bellman‑Ford initializes distances, relaxes all edges |V|‑1 times, then performs one extra pass to detect any further relaxation.
It correctly handles negative edges but reports failure when a reachable negative cycle exists.
The algorithm runs in O(V E) time and uses O(V) extra space.
Vertices unreachable from the source keep a distance of ∞.

Graph Traversals: Breadth-First Search (BFS) vs. Depth-First Search (DFS)

This content contrasts Breadth‑First Search (BFS) and Depth‑First Search (DFS), outlining their traversal order, complexity, and typical use cases.

BFS uses a FIFO queue, visits nodes level by level (A→B→C→D→E→F); DFS uses a LIFO stack, dives deep (A→B→D→E→C→F).
Both run in $O(V+E)$ time; BFS may need $O(V)$ (or $O(b^d)$ ) space, while DFS typically uses $O(d)$ stack depth.
BFS guarantees the shortest path in unweighted graphs, suited for routing, web crawling, and level‑order serialization.
DFS excels in memory‑limited, wide graphs and in tasks like topological sort and cycle detection, but deep recursion can cause stack overflow.

Solving the 0/1 Knapsack Problem: Brute Force, Greedy, Dynamic Programming, and Branch-and-Bound

The 0/1 knapsack problem—selecting whole items to maximize value under capacity  $W$ —is examined through four classic solution strategies: brute‑force, greedy, dynamic programming, and branch‑and‑bound.

Brute force checks all $2^n$ subsets, guaranteeing optimality but with exponential $O(2^n)$ time.
Greedy heuristics (e.g., highest $v_i/w_i$ first) run in $O(n\log n)$ but can miss the optimum because 0/1 knapsack lacks the greedy‑choice property.
Dynamic programming exploits optimal substructure, solving in $O(nW)$ time and $O(nW)$ (or $O(W)$ ) space, yet is pseudo‑polynomial and costly for large $W$ .
Branch‑and‑bound explores a decision tree, pruning nodes via fractional‑knapsack upper bounds; worst‑case $O(2^n)$ but often far faster on favorable instances.

Browse all research articles

Greedy Optimization and Prim’s Minimum Spanning Tree Algorithm

Learning objectives

Footnotes

Prim’s Algorithm in 2 Minutes

1. What is an optimal solution?

Footnotes

Local versus global optimality

2. What does “optimal solution in the greedy approach” mean?

Footnotes

3. Properties of the greedy approach

3.1 Greedy-choice property

3.2 Optimal substructure

3.3 Feasibility preservation

3.4 Irrevocable decisions

3.5 Incremental construction

3.6 Objective-directed selection

3.7 Proof requirement

4. Function of the greedy approach

How to determine whether a greedy method is appropriate

Greedy approach: common questions

5. Minimum spanning trees

6. Prim’s algorithm

Invariant

Footnotes

Prim’s algorithm: manual procedure

7. Applying Prim’s algorithm to the supplied graph

Important when reading the supplied graph

8. Worked Prim trace format

9. Correctness proof for Prim’s algorithm

Claim

Proof

Typical time complexity of Prim’s algorithm

10. Complexity analysis

Footnotes

11. Common mistakes

Exam technique

Greedy algorithms and Prim’s algorithm

What is an optimal solution?

Knowledge Check

Explore Related Topics