✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-113

Prim's Algorithm

Prim's algorithm is a greedy algorithm that constructs a minimum spanning tree by starting from one vertex and repeatedly adding the minimum-weight edge that connects the growing tree to a vertex outside it.

Explanation

Overview

Prim's algorithm finds a minimum spanning tree of a connected, weighted, undirected graph by expanding a single growing tree.

Key concepts

name: Core idea; description: The central focus of prim's algorithm is the capability described here: Prim's algorithm is a greedy algorithm that constructs a minimum spanning tree by starting from one vertex and repeatedly adding the minimum-weight edge that connects the growing tree to a vertex outside it.; name: Problem context; description: Prim's Algorithm is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using prim's algorithm, check its assumptions, input requirements, expected output, and resource constraints.

Time complexity

binaryHeapAndAdjacencyList: O((V + E) log V) with a suitable implementation.; adjacencyMatrix: O(V²); fibonacciHeapTheoretical: O(E + V log V) with a Fibonacci heap.

Space complexity

O(V) auxiliary space for key, parent, visited, and priority-queue structures, excluding graph storage.

Applications

Designing communication networks; Connecting cities with minimum infrastructure cost; Electrical and cable network planning; Building network backbones; Clustering and graph optimization

Advantages

Efficient for many connected weighted graphs.; Naturally grows one tree from a starting vertex.; Works well with adjacency lists and priority queues.; Does not require sorting every edge in advance.

Limitations

Requires an undirected graph for the standard MST problem.; A disconnected graph produces a forest rather than one spanning tree.; Priority-queue management adds implementation complexity.; The result may differ when multiple MSTs have equal total weight.

Example or application

A worked example has not yet been added.

Definition

Prim's algorithm finds a minimum spanning tree of a connected, weighted, undirected graph by expanding a single growing tree.

Problem Type

Minimum Spanning Tree

Graph Requirements

Designed for weighted undirected graphs. For a disconnected graph, it can be restarted in each component to construct a minimum spanning forest.

Core Principle

Always choose the minimum-weight edge crossing from the current tree to a vertex not yet included.

Data Structures

  • Visited set or boolean array

  • Priority queue or min-heap

  • Adjacency list

  • Parent array

  • Key or minimum connection-cost array

Algorithm Steps

  • Choose any starting vertex.

  • Mark it as included in the growing tree.

  • Insert its outgoing edges into a min-priority queue.

  • Select the minimum-weight edge connecting the tree to an unvisited vertex.

  • Add that edge and vertex to the tree.

  • Insert the new vertex's eligible outgoing edges.

  • Continue until all vertices are included.

Key Array

key[v] stores the minimum edge weight currently known for connecting an unvisited vertex v to the growing tree.

Parent Array

parent[v] stores the vertex through which v is connected to the growing tree.

Example Graph

Edges

    • A

    • B

    • 1

    • A

    • C

    • 4

    • B

    • C

    • 2

    • B

    • D

    • 5

    • C

    • D

    • 3

Starting Vertex

A

One Minimum Spanning Tree

    • A

    • B

    • 1

    • B

    • C

    • 2

    • C

    • D

    • 3

Total Weight

6

Time Complexity

Binary Heap And Adjacency List

O((V + E) log V) with a suitable implementation.

Adjacency Matrix

O(V²)

Fibonacci Heap Theoretical

O(E + V log V) with a Fibonacci heap.

Space Complexity

O(V) auxiliary space for key, parent, visited, and priority-queue structures, excluding graph storage.

Negative Weights

Negative edge weights are permitted in minimum spanning tree problems and do not invalidate Prim's algorithm.

Advantages

  • Efficient for many connected weighted graphs.

  • Naturally grows one tree from a starting vertex.

  • Works well with adjacency lists and priority queues.

  • Does not require sorting every edge in advance.

Limitations

  • Requires an undirected graph for the standard MST problem.

  • A disconnected graph produces a forest rather than one spanning tree.

  • Priority-queue management adds implementation complexity.

  • The result may differ when multiple MSTs have equal total weight.

Comparison With Kruskal

Prim

Grows one tree by selecting the cheapest edge crossing the current tree boundary.

Kruskal

Builds a forest by selecting globally sorted edges that do not create cycles.

Typical Use

Prim is often convenient for dense graphs or adjacency-based implementations, while Kruskal is often convenient when edges can be sorted efficiently, especially in sparse graphs.

Applications

  • Designing communication networks

  • Connecting cities with minimum infrastructure cost

  • Electrical and cable network planning

  • Building network backbones

  • Clustering and graph optimization

Common Mistakes

  • Adding an edge whose destination is already in the tree.

  • Confusing the minimum edge weight with the shortest path from the source.

  • Applying the standard algorithm to directed graphs.

  • Failing to restart for disconnected components when a minimum spanning forest is required.

Related Concepts

  • Minimum Spanning Trees

  • Kruskal's Algorithm

  • Priority Queues

  • Binary Heaps

  • Weighted Graphs

Key Concepts

NameDescription

Core idea

The central focus of prim's algorithm is the capability described here: Prim's algorithm is a greedy algorithm that constructs a minimum spanning tree by starting from one vertex and repeatedly adding the minimum-weight edge that connects the growing tree to a vertex outside it.

Problem context

Prim's Algorithm is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using prim's algorithm, check its assumptions, input requirements, expected output, and resource constraints.

Practice Questions

QuestionAnswer

What is the main purpose of prim's algorithm?

Prim's algorithm is a greedy algorithm that constructs a minimum spanning tree by starting from one vertex and repeatedly adding the minimum-weight edge that connects the growing tree to a vertex outside it.

What should be checked before applying prim's algorithm?

For prim's algorithm, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of prim's algorithm be validated?

Trace a representative prim's algorithm case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of prim's algorithm.

  • Identify the assumptions, inputs, and conditions relevant to prim's algorithm.

  • Evaluate an application of prim's algorithm for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures