# Graph — Data Structures & Algorithms

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

> Nodes joined by edges — the model for maps, networks, and dependencies.

## Representation

An **adjacency list** maps each node to its neighbours — `O(V+E)` space, fast to iterate edges. An **adjacency matrix** is a `V×V` grid — `O(V^2)` space but `O(1)` edge lookup. Lists win for sparse graphs (most real ones).

## Cities and roads

Cities are nodes, roads are edges. One-way roads are a directed graph; toll costs are edge weights.

## Build & traverse

A dict of lists is enough. BFS finds shortest paths in unweighted graphs; DFS explores components and cycles.

```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
```

## Algorithm menu

Unweighted shortest path → BFS. Weighted, non-negative → Dijkstra. Ordering with dependencies → topological sort. Connectivity groups → Union-Find or DFS.