# Graph
A **graph** is a structure consisting of a set of vertices (nodes) and a set of edges that connect pairs of vertices. Edges can be **directed** (one-way, like a one-way street) or **undirected** (bidirectional). Edges can carry a **weight** representing cost, distance, or capacity. Graphs model any relationship between entities: road networks, dependency graphs, social networks, circuit netlists, and state machines.

The two standard representations are the **adjacency matrix** and the **adjacency list**.

An adjacency matrix is a 2D [[array]] `adj[u][v]` that stores 1 (or the edge weight) if an edge exists from `u` to `v`, and 0 otherwise. It provides O(1) edge lookup but uses O(V²) memory, which is wasteful for sparse graphs.

```c
int adj[V][V];         // adjacency matrix
adj[u][v] = weight;    // add edge u -> v
```

An adjacency list stores, for each vertex, a list of its neighbours. It uses O(V + E) memory and is preferred for sparse graphs where E << V².

```c
struct edge { int to, weight; };
struct edge *adj[V];   // adj[u] is the list of edges leaving u
int          deg[V];   // number of edges from each vertex
```

The two fundamental traversal algorithms are **breadth-first search** (BFS) and **depth-first search** (DFS). BFS uses a [[queue]] and visits vertices in order of their distance from the source; it finds shortest paths in unweighted graphs. DFS uses a [[stack]] (or recursion) and is the basis for topological sorting, cycle detection, and finding strongly connected components.

**Shortest path algorithms** handle weighted graphs. Dijkstra's algorithm finds the shortest path from a source to all vertices in O((V + E) log V) using a min-[[heap]]. Bellman-Ford handles negative edge weights in O(VE). Floyd-Warshall finds all-pairs shortest paths in O(V³).