आज के समय में अगर आप GATE CS/IT 2026 की तैयारी कर रहे हैं तो Graph Algorithms को strong करना बहुत ज़रूरी है। Graph Algorithms हर साल GATE में 1–2 direct questions और कई बार indirect form में आते ही आते हैं। यही कारण है कि इस article में हम Graph Algorithms को बिल्कुल आसान Hindi में समझेंगे – ताकि beginner से लेकर advanced student तक सभी को benefit हो।
इस complete guide में आप सीखेंगे:
- Graph क्या होता है और उसे कैसे represent करते हैं
- BFS और DFS कैसे काम करते हैं
- Dijkstra Algorithm से shortest path कैसे निकाला जाता है
- Kruskal Algorithm से Minimum Spanning Tree कैसे बनती है
- और साथ में GATE level practice questions
ग्राफ क्या है (What is Graph in Hindi) ?
Graph एक data structure है जो nodes (vertices) और edges (connections) से मिलकर बनता है।
Mathematically हम लिखते हैं:
G = (V, E)
जहाँ
- V = vertices
- E = edges
Example:
- City = Vertex
- Road = Edge
ग्राफ के प्रकार (Types of Graph)
| प्रकार | मतलब |
| Undirected Graph | दोनों तरफ movement possible |
| Directed Graph | एक ही direction में |
| Weighted Graph | हर edge का cost |
| Unweighted Graph | सभी edges equal |
ग्राफ एल्गोरिदम क्या है (What is Graph Algorithms in Hindi) ?
Graph Algorithms वे तकनीकें हैं जिनकी सहायता से हम Graph Data Structure पर विभिन्न प्रकार की समस्याओं को हल करते हैं।
Graph दो मुख्य भागों से मिलकर बनता है:
- Vertices (नोड्स) – बिंदु या वस्तुएँ
- Edges (किनारे) – नोड्स के बीच संबंध
सरल शब्दों में, Graph Algorithms हमें यह पता लगाने में सहायता करते हैं कि:
- सबसे छोटा मार्ग कौन-सा है?
- सभी नोड्स आपस में जुड़े हुए हैं या नहीं?
- न्यूनतम लागत में पूरे नेटवर्क को कैसे जोड़ा जाए?
Graph को Represent कैसे किया जाता है ?
Graph को computer memory में मुख्य रूप से दो तरीकों से represent किया जाता है:
1. Adjacency Matrix Representation
Adjacency Matrix एक 2-D array होती है जिसमें rows और columns दोनों ही vertices को represent करते हैं।
यदि ग्राफ़ में V vertices हैं, तो matrix का size होगा V × V।
A[i][j] = 1 → यदि i से j तक edge है
A[i][j] = 0 → यदि i से j तक कोई edge नहीं है
Example:
यदि vertex 1 और 2 के बीच edge है तो
A[1][2] = 1
विशेषताएँ:
- Memory usage: O(V²)
- Dense graph के लिए उपयुक्त
- Edge exist करता है या नहीं, यह जाँच बहुत तेज़ होती है
2. Adjacency List Representation
Adjacency List में हर vertex के लिए उसके सभी connected vertices की list store की जाती है।
Example:
यदि node 1 से 2 और 3 जुड़े हैं तो
1 → 2 → 3
विशेषताएँ:
- Memory usage: O(V + E)
- Sparse graph के लिए उपयुक्त
- BFS और DFS जैसे Graph Algorithms के लिए सबसे ज़्यादा उपयोग किया जाता है
यह भी पढ़ें: Sorting Algorithms Notes for GATE CS 2026 Aspirants – Complete Guide
Graph Algorithms के प्रकार (Types of Graph Algorithms)
Graph Algorithms को मुख्य रूप से चार भागों में विभाजित किया जाता है:
1. Breadth First Search (BFS) Graph Algorithms
Breadth First Search (BFS) एक महत्वपूर्ण Graph Algorithm है जिसका उपयोग ग्राफ़ को स्तर दर स्तर (level by level) traverse करने के लिए किया जाता है।
इसमें सबसे पहले स्रोत नोड को visit किया जाता है, फिर उसके सभी पड़ोसी नोड्स को एक साथ visit किया जाता है, उसके बाद उनके पड़ोसियों को, और यह प्रक्रिया तब तक चलती रहती है जब तक ग्राफ़ के सभी नोड्स traverse नहीं हो जाते।
BFS में मुख्य रूप से Queue data structure का उपयोग होता है, जिससे नोड्स उसी क्रम में process होते हैं जिस क्रम में वे जोड़े जाते हैं। यह एल्गोरिद्म विशेष रूप से unweighted graph में सबसे छोटा मार्ग (shortest path) खोजने के लिए बहुत उपयोगी होता है और GATE तथा competitive exams में अक्सर पूछा जाता है।
BFS कैसे काम करता है?
BFS graph को level by level traverse करता है और इसके लिए Queue का use होता है।
BFS Algorithm Steps
- Source node को queue में डालो
- उसे visited mark करो
- उसके सभी neighbours queue में डालो
- जब तक queue empty ना हो, repeat
BFS की Time Complexity
O(V + E)
BFS कहाँ use होता है?
- Unweighted graph में shortest path
- Social network connections
- Level order traversal
2. Depth First Search (DFS) Graph Algorithms
Depth First Search (DFS) एक महत्वपूर्ण Graph Algorithm है जिसका उपयोग ग्राफ़ को गहराई में जाकर traverse करने के लिए किया जाता है।
इसमें सबसे पहले किसी एक नोड को visit किया जाता है और फिर उसके किसी एक पड़ोसी नोड की ओर बढ़ते हुए लगातार आगे बढ़ा जाता है, जब तक कि आगे कोई नया नोड न मिले। इसके बाद एल्गोरिद्म वापस लौटकर अन्य रास्तों को explore करता है।
DFS में मुख्य रूप से Stack या Recursion का उपयोग किया जाता है। यह एल्गोरिद्म cycle detection, connected components, maze solving तथा topological sort जैसी समस्याओं को हल करने में बहुत उपयोगी होता है और GATE तथा interviews में बार-बार पूछा जाता है।
DFS कैसे काम करता है?
- Stack या recursion का use
- एक path पूरा explore करो, फिर backtrack
DFS Steps
- Node को visited mark करो
- उसके unvisited neighbours पर DFS call करो
DFS की Time Complexity
O(V + E)
DFS के Uses
- Cycle detection
- Connected components
- Maze solving
- Topological sort
3. Dijkstra Graph Algorithm (Shortest Path Algorithms)
Dijkstra Algorithm एक प्रमुख Graph Algorithm है जिसका उपयोग weighted graph में किसी एक स्रोत नोड से सभी अन्य नोड्स तक का सबसे छोटा मार्ग (shortest path) निकालने के लिए किया जाता है।
यह एल्गोरिद्म इस सिद्धांत पर कार्य करता है कि हर चरण में उस नोड को चुना जाए जिसकी वर्तमान दूरी सबसे कम हो, और फिर उसके पड़ोसी नोड्स की दूरी को update किया जाए। इसमें सामान्यतः Priority Queue (Min Heap) का प्रयोग किया जाता है ताकि न्यूनतम दूरी वाला नोड जल्दी प्राप्त किया जा सके। ध्यान देने योग्य बात यह है कि Dijkstra Algorithm केवल तभी सही परिणाम देता है जब सभी edge weights non-negative हों।
यह एल्गोरिद्म नेटवर्क routing, Google Maps जैसे navigation systems तथा GATE परीक्षा में shortest path से जुड़े प्रश्नों के लिए अत्यंत महत्वपूर्ण है।
कब use करें?
- Graph weighted हो
- Edge weights non-negative हों
Dijkstra Steps
- Source का distance = 0
- बाकी सभी का distance = ∞
- Minimum distance वाला node choose
- उसके neighbours update करो
Time Complexity
O(E log V)
4. Kruskal Graph Algorithms (Minimum Spanning Tree)
Kruskal Algorithm एक महत्वपूर्ण Graph Algorithm है जिसका उपयोग Minimum Spanning Tree (MST) बनाने के लिए किया जाता है। इसका उद्देश्य ग्राफ़ के सभी नोड्स को इस प्रकार जोड़ना होता है कि कुल लागत (total weight) न्यूनतम रहे और किसी भी प्रकार का चक्र (cycle) न बने।
Kruskal Algorithm में सबसे पहले सभी edges को उनके weight के बढ़ते क्रम में sort किया जाता है, इसके बाद एक-एक करके सबसे कम weight वाली edge को चुना जाता है। यदि वह edge cycle नहीं बनाती है, तो उसे MST में शामिल कर लिया जाता है। इस प्रक्रिया में cycle की जाँच के लिए सामान्यतः Disjoint Set Union (Union-Find) data structure का उपयोग किया जाता है। यह एल्गोरिद्म network design, cable laying तथा GATE परीक्षा में minimum cost network से जुड़े प्रश्नों के लिए अत्यंत उपयोगी होता है।
MST क्या होती है?
ऐसा tree जो:
- सभी nodes को connect करे
- Total cost minimum हो
Kruskal Steps
- सभी edges को weight के अनुसार sort करो
- Disjoint Set Union (DSU) बनाओ
- सबसे कम weight edge pick करो
- अगर cycle नहीं बने तो MST में add करो
Time Complexity
O(E log E)
यह भी पढ़ें: Algorithms & Complexity: Big-O, Big-Theta & Big-Omega को आसान भाषा में जानिए
GATE Practice Questions on Graph Algorithms (with Solutions)
नीचे Graph Algorithms – BFS, DFS, Dijkstra और Kruskal से जुड़े 10 महत्वपूर्ण GATE level प्रश्न उनके सही उत्तर और संक्षिप्त समाधान सहित दिए गए हैं।
Q1. BFS Traversal Order
An unweighted undirected graph has the following edges:
(1–2), (1–3), (2–4), (3–5).
If BFS traversal starts from vertex 1, what will be the traversal order?
Answer:
1, 2, 3, 4, 5
Explanation:
BFS visits node 1 first, then its neighbors 2 and 3, and then nodes 4 and 5.
Q2. BFS Shortest Path Length
In an unweighted graph, the edges are:
(1–2), (2–3), (3–5), (1–4), (4–5).
What is the length of the shortest path from node 1 to node 5?
Answer:
2
Explanation:
Shortest path is 1 → 4 → 5 which contains 2 edges.
Q3. DFS Traversal Sequence
A graph has the edges:
(1–2), (1–3), (2–4), (3–5).
If DFS traversal starts from node 1 and the smaller numbered node is chosen first, what are the first four nodes in the traversal?
Answer:
1, 2, 4, 3
Q4. Cycle Detection using DFS
In an undirected graph, if during DFS a visited node is encountered again which is not the parent, what does it indicate?
Answer:
The graph contains a cycle.
Q5. Dijkstra Algorithm – Shortest Path
A weighted graph has the following edges:
1–2 (2), 1–3 (4), 2–3 (1), 2–4 (7), 3–4 (3).
What is the shortest distance from node 1 to node 4?
Answer:
6
Explanation:
Shortest path: 1 → 2 → 3 → 4
Total cost = 2 + 1 + 3 = 6.
Q6. Limitation of Dijkstra Algorithm
Can Dijkstra’s algorithm work correctly if the graph contains negative edge weights?
Answer:
No.
Dijkstra’s algorithm works correctly only when all edge weights are non-negative.
Q7. Kruskal Algorithm – MST Cost
A graph has the following weighted edges:
(1–2, 1), (2–3, 2), (3–4, 3), (4–1, 4), (1–3, 5).
What is the total cost of the Minimum Spanning Tree?
Answer:
6
Explanation:
Edges selected are (1–2), (2–3), (3–4).
Total cost = 1 + 2 + 3 = 6.
Q8. Purpose of Disjoint Set Union
What is the main purpose of using Disjoint Set Union (Union-Find) in Kruskal’s algorithm?
Answer:
To detect cycles and check whether two vertices belong to the same connected component.
Q9. BFS Time Complexity
What is the time complexity of BFS using adjacency list representation?
Answer:
O(V + E)
Q10. Application of DFS
DFS is primarily used for solving which of the following problems?
- A) Shortest path in weighted graph
B) All pairs shortest path
C) Cycle detection
D) Minimum spanning tree
Answer:
C) Cycle detection
यह भी पढ़ें: Trees vs Graphs vs Hash Tables: कब और क्यों चुनें
निष्कर्ष (Conclusion)
इस पूरे लेख में आपने Graph Algorithms के सबसे महत्वपूर्ण concepts – BFS, DFS, Dijkstra और Kruskal – को सरल हिन्दी में समझा। ये सभी Algorithms GATE 2026 CS&IT की तैयारी के लिए अत्यंत आवश्यक हैं क्योंकि इन्हीं से जुड़े प्रश्न लगभग हर वर्ष पूछे जाते हैं।
BFS और DFS आपको ग्राफ़ को सही तरीके से traverse करना सिखाते हैं, Dijkstra weighted graph में shortest path निकालने में सहायता करता है, और Kruskal Algorithm minimum cost में पूरा network जोड़ने की तकनीक बताता है।
यदि आप इन चारों algorithms के logic, working steps और practice problems पर नियमित अभ्यास करते हैं, तो न केवल आपका GATE score बेहतर होगा बल्कि interviews और real-world programming problems को हल करना भी बहुत आसान हो जाएगा।
इसलिए, Graph Algorithms को केवल पढ़ने तक सीमित न रखें, बल्कि बार-बार revise करें और स्वयं से समस्याएँ हल करके इस topic में mastery प्राप्त करें।
यह भी पढ़ें:
