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
Learn Kruskal\
The Approach
Kruskal's algorithm finds the MST with a beautifully simple greedy strategy:
- Sort all edges by weight (smallest first)
- For each edge, if it connects two different components, add it to MST
- Stop when MST has V-1 edges
The key challenge is step 2: how do we efficiently check if two vertices are already in the same component? The answer is Union-Find (Disjoint Set Union), which makes this check nearly O(1).
Algorithm Steps
Example
Sort edges by weight ascending
Initialize Union-Find with V components
mst_edges = []
For each edge (u, v, weight) in sorted order:
If find(u) != find(v): // u and v in different components
union(u, v) // merge their components
mst_edges.append(edge)
If len(mst_edges) == V-1:
break // MST complete
Step-by-Step Example
| Step 1: Edge (2,3,1) — vertices 2,3 in different sets | ADD |
| Components | {0}{1}{2,3}{4}{5} MST weight: 1 |
| Step 2: Edge (0,1,2) — vertices 0,1 in different sets | ADD |
| Components | {0,1}{2,3}{4}{5} MST weight: 3 |
| Step 3: Edge (1,3,3) — vertex 1 in {0,1}, vertex 3 in {2,3} | ADD |
| Components | {0,1,2,3}{4}{5} MST weight: 6 |
| Step 4: Edge (0,2,4) — vertices 0,2 both in {0,1,2,3} | SKIP (cycle!) |
| Step 5: Edge (3,4,5) — vertex 3 in {0,1,2,3}, vertex 4 in {4} | ADD |
| Components | {0,1,2,3,4}{5} MST weight: 11 |
| Step 6: Edge (4,5,6) — vertex 4 in {0,1,2,3,4}, vertex 5 in {5} | ADD |
| Components | {0,1,2,3,4,5} MST weight: 17 |
| MST edges | (2,3,1), (0,1,2), (1,3,3), (3,4,5), (4,5,6) |
| Total weight | 17 |
Python Implementation
Example
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
# Union by rank
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def kruskal(num_vertices, edges):
"""
edges: list of (weight, u, v) tuples
Returns: list of MST edges and total weight
"""
edges.sort() # Sort by weight
uf = UnionFind(num_vertices)
mst = []
total_weight = 0
for weight, u, v in edges:
if uf.union(u, v): # Returns True if merged (no cycle)
mst.append((u, v, weight))
total_weight += weight
if len(mst) == num_vertices - 1:
break
return mst, total_weight
# Example
edges = [(1,2,3), (2,0,1), (3,1,3), (4,0,2), (5,3,4), (6,4,5), (7,1,2), (8,3,5)]
mst, weight = kruskal(6, edges)
print(f"MST edges: {mst}")
print(f"Total weight: {weight}")
C++ Implementation
Example
#include <vector>
#include <algorithm>
using namespace std;
class UnionFind {
vector<int> parent, rank_;
public:
UnionFind(int n) : parent(n), rank_(n, 0) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool unite(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (rank_[px] < rank_[py]) swap(px, py);
parent[py] = px;
if (rank_[px] == rank_[py]) rank_[px]++;
return true;
}
};
struct Edge { int u, v, weight; };
pair<vector<Edge>, int> kruskal(int V, vector<Edge>& edges) {
sort(edges.begin(), edges.end(),
[](const Edge& a, const Edge& b) { return a.weight < b.weight; });
UnionFind uf(V);
vector<Edge> mst;
int totalWeight = 0;
for (auto& e : edges) {
if (uf.unite(e.u, e.v)) {
mst.push_back(e);
totalWeight += e.weight;
if (mst.size() == V - 1) break;
}
}
return {mst, totalWeight};
}
Time and Space Complexity
- Time: O(E log E) for sorting + O(E × α(V)) for Union-Find operations ≈ O(E log E)
- Since E ≤ V², log E ≤ 2 log V, so this is also O(E log V)
- α(V) is the inverse Ackermann function, practically constant (~4)
- Space: O(V + E) — Union-Find uses O(V), edge list uses O(E)
Kruskal's vs Prim's
| Aspect | Kruskal's | Prim's |
|---|---|---|
| Strategy | Sort edges, add safely | Grow tree from vertex |
| Data structure | Union-Find | Priority Queue |
| Time | O(E log E) | O(E log V) |
| Best for | Sparse graphs (E ≈ V) | Dense graphs (E ≈ V²) |
| Edge list input | Natural fit | Needs adjacency list |
| Parallelizable | Yes (independent edge checks) | Less so |
Why Kruskal's is Correct
Kruskal's works because of the cut property: at each step, the lightest edge connecting two different components crosses some cut of the graph. By the cut property, this edge must be in the MST. Since we process edges in weight order, we always pick the correct minimum crossing edge for each cut we encounter.
Applications
- Network design: Minimum cost to connect all nodes (cable, pipe, road)
- Clustering: Remove the k-1 heaviest MST edges to get k clusters
- Approximation: 2-approximation for metric TSP
- Image segmentation: Pixels as vertices, similarity as edge weights
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Kruskal\.
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, kruskals, 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.GraphsPrim\Master Prim\