Kruskal Algorithm vs Prim Algorithm
| Feature | Kruskal Algorithm | Prim Algorithm |
|---|---|---|
| Type | Edge-based | Vertex-based |
| Main Idea | Graph के सारे edges को ascending weight में sort कर के MST बनाना | किसी start vertex से शुरू कर के nearest unvisited vertex add करके MST बनाना |
| Suitable Graph | Sparse Graphs (कम edges वाले) | Dense Graphs (ज्यादा edges वाले) |
| Data Structure Used | Union-Find / Disjoint Set | Min-Heap / Priority Queue या adjacency matrix/list |
| Step-by-Step Working |
1. सभी edges को weight ascending order में sort करो 2. सबसे छोटा edge select करो 3. Cycle create न हो तो edge add करो 4. Repeat until V-1 edges selected |
1. कोई एक start vertex select करो 2. Minimum weight वाला adjacent edge select करो जो unvisited vertex को जोड़ता हो 3. Vertex add करो और edge mark करो 4. Repeat until सभी vertices included |
| Cycle Handling | Union-Find structure से cycle avoid होती है | Automatic, क्योंकि हमेशा unvisited vertex select होता है |
| Starting Point | किसी भी edge से | किसी भी vertex से |
| Edge Selection Order | Global minimum edge first (Graph के सभी edges को consider) | Local minimum edge next (adjacent vertices से select) |
| Time Complexity | O(E log E) (edges sort के लिए) | O(V^2) normal, O(E + V log V) optimized (Min-Heap के साथ) |
| Space Complexity | O(V + E) | O(V^2) / O(V + E) |
| Implementation Difficulty | Easy for sparse graphs, Union-Find समझना जरूरी | Easy for dense graphs, Min-Heap या adjacency matrix समझना जरूरी |
| Pros | Sparse graphs में fast- Forest (multiple components) handle कर सकता है- Simple edge-based approach | Dense graphs में fast- Always nearest vertex select करता है- Vertex-based growth easy to track |
| Cons | Dense graphs में slow- Union-Find complex लगता है beginner को | Sparse graphs में Kruskal से slow- Min-Heap या adjacency matrix समझना जरूरी |
| Applications | Rural electricity/fiber-optic networks- Sparse road networks- ISRO sparse satellite networks | Dense city metro/road networks (Mumbai Metro)- Dense telecommunications networks- Urban planning for water/gas/electricity |
| Example Scenario | भारत के गाँवों में fiber optic connection, जहाँ sparse edges हैं | Mumbai Metro network planning, dense city connections |
| Result | MST generate करता है, sometimes multiple MST possible | MST generate करता है, multiple MST possible लेकिन total weight same |
DFS vs BFS
| Feature | DFS (Depth First Search) | BFS (Breadth First Search) |
|---|---|---|
| Definition | DFS एक graph/tree traversal algorithm है जो depth में जाकर node explore करता है। | BFS भी एक graph/tree traversal algorithm है जो level-wise या breadth-wise nodes explore करता है। |
| Traversal Method | Stack का use करता है (या recursion) | Queue का use करता है |
| Order of Traversal | एक path को पूरा explore करता है फिर backtrack करता है | एक level के सभी nodes visit करता है, फिर next level पर जाता है |
| Use Case | Path finding, Topological Sorting, Cycle Detection, Maze solving | Shortest path in unweighted graph, Level-order traversal, Social network search |
| Memory Usage | कम memory अगर graph sparse है, recursion stack depend करता है | ज्यादा memory अगर graph wide है, क्योंकि queue में level के सारे nodes store होते हैं |
| Time Complexity | O(V + E) (V = vertices, E = edges) | O(V + E) |
| Space Complexity | O(V) recursion stack के लिए | O(V) queue के लिए |
| Behavior | Deep exploration first | Level by level exploration |
Dijkstra’s Algorithm VS Bellman-Ford Algorithm VS Floyd-Warshall Algorithm
Feature | Dijkstra Algorithm | Bellman-Ford Algorithm | Floyd-Warshall Algorithm |
Purpose | Single-source shortest path (non-negative edges) – यानी किसी start vertex से सभी reachable vertices तक shortest distance निकालना | Single-source shortest path with negative edges – negative weights handle करता है और negative cycles detect करता है | All-pairs shortest path – ग्राफ में हर vertex pair के बीच shortest path निकालता है |
Graph Type | Weighted, directed/undirected, non-negative weights | Weighted, directed/undirected, negative weights allowed | Weighted, directed/undirected, negative weights allowed (लेकिन negative cycles नहीं) |
Data Structure | Min-priority queue (Heap) | Simple distance array | 2D Distance matrix (dist[][]) |
Time Complexity | O((V + E) log V) with heap O(V²) simple implementation | O(V × E) | O(V³) |
Space Complexity | O(V + E) | O(V) | O(V²) |
Negative weight edges | Not allowed | Allowed | Allowed (लेकिन negative cycles नहीं) |
Negative cycle detection | नहीं | हाँ | नहीं |
Single-source vs All-pairs | Single-source | Single-source | All-pairs |
Applications | GPS navigation, network routing, weighted graphs में shortest path | Financial networks, credit/debit networks, graphs with negative weights | Traffic analysis, small-medium networks, complete graph analysis |
Advantages | Positive weighted graphs में fast, guaranteed shortest path | Negative weights handle कर सकता है, negative cycles detect कर सकता है | हर vertex pair के बीच shortest path निकालता है, negative weights support करता है |
Limitations | Negative weights handle नहीं करता | बड़े graphs में slow | Time & space complexity बहुत high, बड़े graphs के लिए unsuitable |
