Graphs
Graph एक non-linear data structure है, जिसमें objects को vertices (nodes) द्वारा और उनके relations को edges (links) द्वारा represent किया जाता है। यह real-world relationships और networks को represent करने के लिए उपयोग किया जाता है।
Formal Definition :
A Graph G = is a collection of (V, E) :-
V = vertices का set
E = edges का set
सरल शब्दों में : Graph ऐसे data का समूह है, जिसमें कई points (nodes) होते हैं, और उनके बीच relation या connection को edges कहते हैं।
Example :
- Google Maps → Cities = vertices, Roads = edges
- Facebook → Users = vertices, Friend connections = edges
Why Graph is Important? (Graph क्यों ज़रूरी है?)
Graph Data Structure इसलिए महत्वपूर्ण ,है क्योंकि यह उन situations को represent करता है, जहाँ data elements के बीच के connections या relationships, data से भी ज्यादा महत्वपूर्ण होते हैं। Linear structures जैसे Array, Stack या Queue सिर्फ एक direction में data दिखाते हैं, लेकिन Graph multi-directional और complex connections को naturally show कर सकता है। जैसे :
- Shortest Path Problems : Google Maps में fastest route निकालने के लिए Graph का उपयोग होता है।
- Network Routing : Internet पर data packets किस रास्ते जाएँगे—यह Graph algorithms decide करते हैं।
- Recommendation Systems : YouTube/Netflix में “similar content” दिखाने के लिए Graph-based connections analyze होते हैं।
- Social Network Analysis : Friends, followers, connections—all are represented as Graph links.
- Project Scheduling (PERT/CPM) : Big projects के tasks और dependencies को Graph के रूप में manage किया जाता है।
- Airline Route Optimization : Airports और उनके routes को Graph में represent करके best flight path निकाला जाता है।
Types of Graph in Data Structure
1. Directed Graph (Digraph)
Directed Graph वह graph होता है, जिसमें हर edge एक fixed direction रखती है। हर connection one-way माना जाता है, यानी A → B का मतलब सिर्फ A से B तक पहुँचा जा सकता है, B से सीधे A तक नहीं।
Key Points
- हर edge को arrow द्वारा दिखाते हैं
- Relations हमेशा directional होते हैं
- In-degree और Out-degree महत्वपूर्ण concepts हैं
Example : Instagram follow A follows B ≠ B follows A
2. Undirected Graph
Undirected Graph वह ग्राफ है, जिसमें edges के ऊपर कोई direction नहीं होता। दो vertices यदि connected हैं, तो connection दोनों दिशाओं में समान माना जाता है।
Key Points
- Edges को line द्वारा show करते हैं
- Relation हमेशा mutual होता है
- Degree = number of connections
Example : Facebook Friends (दोनों एक-दूसरे के friend)
3. Weighted Graph
Weighted Graph वह graph है, जिसमें हर edge के साथ एक numerical value (cost, distance, time, price) जोड़ा होता है। यह value बताती है, कि उस connection से गुजरने में कितना cost लगेगा।
Key Points
- Weight = edge का cost
- shortest path algorithms में उपयोग
- Positive या negative weight हो सकते हैं
Example : Google Maps distance, Flight ticket price between cities
4. Unweighted Graph
इस graph में edges के साथ कोई cost या weight नहीं होता। Edges सिर्फ दिखाते हैं कि दो nodes connected हैं।
Key Points
- connectivity important
- Weight = Not required
5. Multi Graph
Multi Graph ऐसा graph होता है, जिसमें एक ही pair of vertices के बीच multiple edges हो सकती हैं। इसका उपयोग तब किया जाता है जब दो nodes के बीच अलग-अलग प्रकार के connections मौजूद हों।
Example : City A ↔ City B के बीच
- Bus route
- Train route
- Flight route
6. Complete Graph (Kn)
Complete Graph वह graph होता है, जिसमें हर vertex हर दूसरे vertex से directly connected होता है। यदि graph में n vertices हों, तो edges की संख्या = n(n–1)/2 होती है।
Key Points
- Maximum possible connections
- Fully interconnected network
Example : LAN network जहाँ हर computer direct connect हो।
7. Cyclic Graph
यदि graph में ऐसा path मौजूद हो जो किसी vertex से शुरू होकर घूमते-घूमते वापस उसी vertex पर आ जाए, तो उसे cycle कहते हैं। ऐसे graph को cyclic graph कहा जाता है।
Example : Metro की circular routes
8. Directed Acyclic Graph (DAG)
DAG एक ऐसा directed graph है, जिसमें direction तो होता है, लेकिन किसी भी तरह की cycle नहीं बन सकती। यह सबसे powerful graph types में से एक है, क्योंकि यह dependencies show करने में सबसे perfect है।
Example : Compiler optimization, Project scheduling, Git version control
9. Subgraph
Subgraph वह graph है, जो किसी बड़े graph के कुछ vertices और edges को लेकर बनाया जाता है। Original graph की properties इसमें बनी रहती हैं।
10. Connected Graph
Connected Graph वह graph है, जिसमें किसी भी vertex से किसी भी दूसरे vertex तक जाने का कम से कम एक path मौजूद हो।
Key Points
- No isolated vertices
- Continuous network
Graph Terminology
|
Terminology (शब्द) |
Definition / Meaning (परिभाषा व अर्थ) |
|
Graph |
Nodes (vertices) और उनके connections (edges) से बना non-linear data structure। |
|
Vertex (Node) |
Graph में data रखने वाला बिंदु। जैसे—City, User, Website आदि। |
|
Edge |
दो vertices के बीच का connection या link। |
|
Adjacent Vertices |
दो vertices जो direct edge द्वारा जुड़े हों। |
|
Degree of Vertex |
किसी vertex से जुड़ी कुल edges की संख्या। |
|
In-Degree |
Directed graph में किसी vertex की ओर आने वाली edges की संख्या। |
|
Out-Degree |
Directed graph में किसी vertex से बाहर जाने वाली edges की संख्या। |
|
Path |
एक vertex से दूसरे vertex तक जाने वाली vertices/edges की sequence। |
|
Simple Path |
ऐसा path जिसमें कोई vertex दो बार repeat न हो। |
|
Component |
Disconnected graph के connected parts। |
|
Tree (as Graph) |
Acyclic connected graph |
Applications of Graph (ग्राफ के उपयोग)
- Social Networks : Facebook, Instagram, LinkedIn जैसे platforms में users को nodes और उनके relationships को edges के रूप में represent किया जाता है।
- Computer Networks : Routers, switches और devices nodes होते हैं, और उनके बीच data routes edges की तरह काम करते हैं।
- Google Maps / Navigation Systems : Cities = Nodes और Roads = Edges; shortest path (Dijkstra) जैसी algorithms का उपयोग होता है।
- Web Page Ranking (Google PageRank) : Websites और hyperlinks को graph की तरह analyze किया जाता है जिससे ranking तय हो सके।
- Transportation Systems : Flights, bus routes, train networks graph structure में मॉडल किए जाते हैं।
- Recommendation Systems : User behavior graph के रूप में link किया जाता है ताकि personalized suggestions दिए जा सकें।
- Electrical Circuits Representation : Circuit components = Nodes और their connections = Edges (graph theory का उपयोग circuit analysis में होता है)।
- Database Schema Design : Tables के बीच relationships को graph model में represent किया जाता है |
- AI & Machine Learning : Entities और relationships को graph format में represent किया जाता है, जैसे Google Knowledge Graph।
- Network Flow Problems : traffic flow, data flow जैसे problems को graph theory से solve किया जाता है।
Advantages of Graph (ग्राफ के लाभ)
- Can Represent Complex Data : Graph ऐसे relationships और connections को भी दिखा सकता है जिन्हें arrays या trees handle नहीं कर पाते।
- Best Structure for Many-to-Many Relationships : Social networks, transport routes जैसे systems में multiple connections को आसानी से represent करता है।
- Makes Path Finding Easier : BFS, DFS, Dijkstra जैसी algorithms की मदद से shortest route या reachable nodes खोजे जा सकते हैं।
- Powerful in Network Analysis : Graph से network की connectivity, central nodes, weak points जैसी जानकारी जल्दी मिल जाती है।
- Visualization Friendly : Graph diagrams real-world connections को visually आसान बनाते हैं, जिससे समझने में समय कम लगता है।
- Dynamic & Scalable Structure : Nodes या edges जोड़ना/हटाना बहुत easy होता है, इसलिए large और growing systems में useful है।
- Cycle and Dependency Detection : Graph में cycles, loops या dependency chains detect करना सरल होता है—OS, compilers में उपयोगी।
- Helpful in Optimization Problems : Minimum spanning tree, max flow, shortest path जैसे optimization solutions graphs पर ही आधारित होते हैं।
- Ideal in Recommendation Systems : User–item relationships को graph के रूप में analyze करके Amazon/Netflix जैसे सिस्टम recommendations बनाते हैं।
Disadvantages of Graph (ग्राफ की कमियाँ)
- Complex Implementation: Graph structure को implement करना आसान नहीं होता क्योंकि इसमें multiple nodes, pointers और edges manage करने पड़ते हैं।
- High Memory Usage: Adjacency list या matrix दोनों में कई pointers और connections store होते हैं, जिससे memory usage बढ़ जाती है।
- Difficult Traversal: BFS/DFS जैसे traversals simple trees की तुलना में ज्यादा समय और resources लेते हैं।
- Hard to Visualize for Large Graphs: छोटे graphs सरल दिखते हैं, लेकिन लाखों nodes वाले graphs को समझना और visualize करना मुश्किल हो जाता है।
- High Algorithm Complexity: Shortest path, spanning tree, max-flow जैसी graph algorithms complex होती हैं और high time complexity रखती हैं।
- Data Maintenance Challenging: अगर nodes या edges बार-बार update हों, तो graph structure को maintain करना कठिन और slow हो सकता है।
- Real-Time Processing Tough: Large-scale graphs (जैसे social media graph) पर real-time computation बहुत heavy और costly होता है।
- Cycle Handling Issues: Cycles मौजूद होने से कुछ algorithms को extra steps और checks की ज़रूरत पड़ती है, जिससे performance घटती है।
