Author: devangini123

🌙 Problem Statement: There are n computers numbered from 0 to n-1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network. You are given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected. If it is…

🌙 Comparison – Prim’s vs Kruskal Algorithm

🌙 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