Author: devangini123

🌙 Example: Sorted Edges: 1 → 0, 1 2 → 3, 2 3 → 4, 3 2 → 5, 6 2 → 4, 7 0 → 2, 8 1 → 2, 9 4 → 5, 10 Exploring Edges 1 → 0, 1 2 → 3, 2 3 → 4, 3 2 → 5, 6 2 → 4, 7 Cycle Detected (Skip) 0 → 2, 8 1 → 2, 9 Cycle Detected (Skip) 4 → 5, 10 Cycle Detected (Skip) MST => 1 + 2 + 3 + 6 + 8 => 20 Code JavaScript Python Java C++ C C# class…

🌙 Kruskal’s Algorithm It is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph. Points to Remember: Sort all the edges (ascending order). Create union find for all ‘n’ node. if no cycle, add to (uf). if cycle, skip. Stop when MST has (n-1) edges. Example 1: Sorted Edges: 0 → 3, 1 ✅ 0 → 1, 2 ✅ 1 → 3, 3 ❌ Cycle (Skip) 1 → 2, 3 ✅ 0 → 4, 4 ✅ 3 → 2, 5 ❌ Cycle (Skip) 1 → 5, 7 ✅ There are no more…

🌙 Disjoint Set (Find and Union) Set1: {A, B, C} Set2: {D, E} Set3: {F, G, H} Operations 1. Find: Finds the representative (root/parent) of the set to which an element belongs. Example: Find(B):Set1 Find(D):Set2 Find(H):Set3 2. Union: Merges two different sets into one. Example: Create a edge between [B, D]. As B ∈ Set1 and D ∈ Set2 Set1 and Set2 are merged. All elements of both sets now belong to one common set. This set is represented by one root (leader). Note: If both values belong to the same set, performing a union operation is not needed. Both(Find…

🌙 Prim’s Algorithm Initial Priority Queue: Code JavaScript Python Java C++ C C# class MinPriorityQueue { constructor(config) { this.priority = config.priority; this.heap = []; } isEmpty() { return this.heap.length === 0; } enqueue(element) { this.heap.push(element); this._bubbleUp(); } dequeue() { if (this.isEmpty()) return null; const top = this.heap[0]; const last = this.heap.pop(); if (!this.isEmpty()) { this.heap[0] = last; this._bubbleDown(); } return { element: top }; } _bubbleUp() { let i = this.heap.length – 1; while (i > 0) { let parent = Math.floor((i – 1) / 2); if (this.priority(this.heap[i]) < this.priority(this.heap[parent])) { [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]]; i = parent; }…

🌙 Prim’s Algorithm The purpose of this algorithm is to find the Minimum Spanning Tree (MST) of a connected, undirected, weighted graph. Start from any node and grow tree outwards, always pick the cheapest edge from already built-tree. Here, we take 5 as node. MST: 17 Taking 3 as node. MST: 17

🌙 Minimum Spanning Tree Spanning Tree It is a subgraph that connects all vertuces of the graph with no cycles and exactly n-1 edges. Points to Remember: All Nodes Connected No Cycles (n-1) edges Cost: 7 + 2 + 6 + 3 + 8 = 26 Minimum Spanning Tree Spaaning Tree Minimum Cost Spanning Tree:5 + 1 + 2 + 3 + 8 = 19 Why Minimum Spanning Tree? Minimum edges to connect a network. No Cycles. Simplify the Structure. Use Case: Network Routing Broadcasting Infrastructure design (roads, pipes, electricity) Minimum Spanning Tree Algorithms This will be covered in upcoming…

🌙 Floyd Warshall – Code Code JavaScript Python Java C++ C C# function floydWarshall(V, edges) { // Initial dist array const dist = Array.from({ length: V }, (_, i) => Array.from({ length: V }, (_, j) => (i === j ? 0 : Infinity)) ); // Fill initial distances from edges for (let [i, j, w] of edges) { dist[i][j] = w; } // Floyd-Warshall algorithm for (let k = 0; k < V; k++) { for (let i = 0; i < V; i++) { for (let j = 0; j < V; j++) { dist[i][j] = Math.min( dist[i][k]…

🌙 Comparing all Shortest Path Graph Algorithms Practice Questions Which algorithm is suitable for the scenarios below? Unweighted Graph – BFS Weighted Graph Positive edges – Dijkstra’s Algorithm Weighted Graph Negative edges – Bellman Ford Algorithm Shortest Path between every pair – Floyd Warshall Algorithm Need to find Negative weight cycle – Bellman Ford Algorithm Very large graph, fast real-time results – Dijkstra’s Algorithm Small dense graph (matrix form) – Floyd Warshall Algorithm

🌙 Dijkstra’s Algorithm Code JavaScript Python Java C++ C C# class MinHeap { constructor() { this.heap = []; } parent(i) { return Math.floor((i – 1) / 2); } left(i) { return 2 * i + 1; } right(i) { return 2 * i + 2; } size() { return this.heap.length; } swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; } push(pair) { this.heap.push(pair); this.heapifyUp(); } heapifyUp() { let i = this.heap.length – 1; while (i > 0 && this.heap[i][0] this.heap[this.parent(i)][0]) { this.swap(i, this.parent(i)); i = this.parent(i); } } pop() { if (this.heap.length === 0) return null; if (this.heap.length === 1)…

🌙 Shortest Path – Bellman Ford Algorithm It handles negative edges. Relaxation is the process of trying to improve (reduce) the shortest distance to a vertex using an edge. How Relaxation Works? For an edge u → v with weight w: If distance[u] + w < distance[v] distance[v] = distance[u] + w Why relaxation is repeated in Bellman–Ford? Bellman–Ford relaxes all edges V−1 times. Because the longest possible shortest path can have at most V−1 edges. Each relaxation gradually propagates shorter paths across the graph. First Relaxation Process Updated Values: Second Relaxation Process Updated Values: Third Relaxation Process Updated Values:…