# Graph — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/graph

> Edge से जुड़े nodes — नक्शे, नेटवर्क और निर्भरताओं का मॉडल।

## प्रतिनिधित्व

**Adjacency list** हर node को उसके पड़ोसियों से मैप करती है — `O(V+E)` स्थान, edge पर तेज़ पुनरावृत्ति। **Adjacency matrix** `V×V` grid है — `O(V^2)` स्थान पर `O(1)` edge lookup। Sparse graphs (अधिकांश असली) के लिए list बेहतर।

## शहर और सड़कें

शहर nodes, सड़कें edges। एकतरफ़ा सड़कें directed graph; टोल लागत edge weight।

## बनाएँ और traverse करें

list का dict काफ़ी है। BFS अभारित graph में सबसे छोटा पथ खोजता है; DFS components और cycle खोजता है।

```python
from collections import defaultdict, deque
g = defaultdict(list)
for u, v in edges:
    g[u].append(v)
    g[v].append(u)   # undirected

def bfs(start):
    seen, q = {start}, deque([start])
    while q:
        node = q.popleft()
        for nb in g[node]:
            if nb not in seen:
                seen.add(nb)
                q.append(nb)
    return seen
```

## एल्गोरिदम मेन्यू

अभारित सबसे छोटा पथ → BFS। भारित, गैर-ऋणात्मक → Dijkstra। निर्भरता के साथ क्रम → topological sort। कनेक्टिविटी समूह → Union-Find या DFS।