DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master Prim\
The Approach
While Kruskal's processes edges globally, Prim's grows the MST one vertex at a time. Starting from any vertex, it repeatedly adds the cheapest edge that connects a vertex IN the tree to a vertex NOT in the tree. Think of it like growing a crystal — at each step, the closest atom attaches to the existing structure.
Algorithm Steps
Example
1. Start with any vertex in the MST set
2. Maintain a priority queue of edges from MST to non-MST vertices
3. Extract minimum-weight edge from PQ
4. If the destination vertex is not yet in MST:
a. Add it to MST
b. Add all its edges to non-MST vertices into PQ
5. Repeat until MST has V vertices
Step-by-Step Example
Graph
0 --2-- 1 --3-- 2
| | |
6 8 5
| | |
3 --9-- 4 --7-- 5
Start from vertex 0
MST = {0}, PQ = [(2,0,1), (6,0,3)]
Step 1: Pop (2,0,1) → add vertex 1
MST = {0,1}, add edges from 1: (3,1,2), (8,1,4)
PQ = [(3,1,2), (6,0,3), (8,1,4)]
Step 2: Pop (3,1,2) → add vertex 2
MST = {0,1,2}, add edges from 2: (5,2,5)
PQ = [(5,2,5), (6,0,3), (8,1,4)]
Step 3: Pop (5,2,5) → add vertex 5
MST = {0,1,2,5}, add edges from 5: (7,5,4)
PQ = [(6,0,3), (7,5,4), (8,1,4)]
Step 4: Pop (6,0,3) → add vertex 3
MST = {0,1,2,5,3}, add edges from 3: (9,3,4)
PQ = [(7,5,4), (8,1,4), (9,3,4)]
Step 5: Pop (7,5,4) → add vertex 4
MST = {0,1,2,5,3,4} — all vertices included!
MST edges: (0,1,2), (1,2,3), (2,5,5), (0,3,6), (5,4,7)
Total weight: 2+3+5+6+7 = 23
Python Implementation
Example
import heapq
def prim(graph, start=0):
"""
graph: dict or list of adjacency lists {vertex: [(neighbor, weight), ...]}
Returns: list of MST edges and total weight
"""
V = len(graph)
visited = set([start])
mst_edges = []
total_weight = 0
# Add all edges from start vertex to priority queue
edges = [(weight, start, neighbor) for neighbor, weight in graph[start]]
heapq.heapify(edges)
while edges and len(visited) < V:
weight, u, v = heapq.heappop(edges)
if v in visited:
continue
# Add vertex v to MST
visited.add(v)
mst_edges.append((u, v, weight))
total_weight += weight
# Add edges from v to unvisited vertices
for neighbor, w in graph[v]:
if neighbor not in visited:
heapq.heappush(edges, (w, v, neighbor))
return mst_edges, total_weight
# Example usage
graph = {
0: [(1, 2), (3, 6)],
1: [(0, 2), (2, 3), (4, 8)],
2: [(1, 3), (5, 5)],
3: [(0, 6), (4, 9)],
4: [(1, 8), (3, 9), (5, 7)],
5: [(2, 5), (4, 7)]
}
mst, weight = prim(graph)
print(f"MST: {mst}") # [(0,1,2), (1,2,3), (2,5,5), (0,3,6), (5,4,7)]
print(f"Weight: {weight}") # 23
C++ Implementation
Example
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> Edge; // weight, from, to
pair<vector<Edge>, int> prim(vector<vector<pii>>& graph, int start = 0) {
int V = graph.size();
vector<bool> visited(V, false);
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
vector<Edge> mst;
int totalWeight = 0;
visited[start] = true;
for (auto [neighbor, weight] : graph[start])
pq.push({weight, start, neighbor});
while (!pq.empty() && mst.size() < V - 1) {
auto [w, u, v] = pq.top();
pq.pop();
if (visited[v]) continue;
visited[v] = true;
mst.push_back({w, u, v});
totalWeight += w;
for (auto [neighbor, weight] : graph[v])
if (!visited[neighbor])
pq.push({weight, v, neighbor});
}
return {mst, totalWeight};
}
Time and Space Complexity
- With binary heap: O(E log V) — each edge is pushed/popped from heap at most once
- With Fibonacci heap: O(E + V log V) — decrease-key is O(1) amortized
- Space: O(V + E) — for visited set and priority queue
Prim's vs Kruskal's: When to Use Which
Choose Prim's when:
- Graph is dense (E close to V²)
- Graph is given as adjacency list/matrix
- You want to grow MST from a specific starting point
Choose Kruskal's when:
- Graph is sparse (E close to V)
- Edges are given as a list (easy to sort)
- You want parallelizable computation
In competitive programming, both work well. Prim's with adjacency list is slightly more natural for dense graphs. Kruskal's is easier to implement correctly (sort + Union-Find).
Correctness: Why Prim's Works
At each step, Prim's considers the cut between MST vertices and non-MST vertices. The minimum-weight edge crossing this cut is added. By the cut property, this edge must be in the MST. Since Prim's always picks the minimum crossing edge (via priority queue), it correctly builds the MST.
Practical Tips
- Lazy vs Eager Prim's: The implementation above is "lazy" — it pushes duplicate edges and skips stale ones. An "eager" version tracks the best edge to each non-MST vertex and updates it, avoiding duplicates but requiring a decrease-key operation.
- Dense graphs with matrix: For very dense graphs, a simple O(V²) version without a heap works well — just scan all non-MST vertices for the minimum key at each step.
- Starting vertex doesn't matter: The MST is the same regardless of which vertex you start from (assuming unique edge weights).
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Prim\.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, graphs, prims, algorithm
Related Data Structures & Algorithms Topics
Continue learning this concept
GraphsBellman-Ford AlgorithmLearn Bellman-Ford shortest path algorithm that handles negative edge weights, detects negative cycles, with complete implementation and analysis.GraphsBreadth-First Search (BFS) AlgorithmLearn BFS traversal with queue-based implementation, level-order processing, shortest path in unweighted graphs, and real applications.GraphsDepth-First Search (DFS) AlgorithmMaster DFS traversal using recursion and stack, understand pre/post ordering, cycle detection, and connected component discovery.GraphsDijkstra\Master Dijkstra\GraphsFloyd-Warshall AlgorithmMaster the all-pairs shortest path algorithm using dynamic programming with three nested loops, path reconstruction, and practical applications.GraphsKruskal\Learn Kruskal\