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.

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².

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³).