concept · INFO-CS-ADS-113Prim'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
One Minimum Spanning Tree
Time Complexity
Binary Heap And Adjacency List
O((V + E) log V) with a suitable implementation.
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
| Name | Description |
|---|
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
| Question | Answer |
|---|
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