Graphs

What it is

A graph is a set of nodes (vertices) connected by edges, which may be directed or undirected, weighted or unweighted. A tree is a special case of a graph (connected, acyclic, one path between any two nodes) — graphs drop those restrictions.

Representations

• Adjacency list — a hash map/array of node → list of neighbors. Space O(V + E), and the standard choice for sparse graphs.
• Adjacency matrix — a V×V grid of edge presence/weight. O(V²) space, but O(1) edge lookup — worth it only for dense graphs.

Traversal

• DFS — recurse into a neighbor before backtracking; natural fit for path-existence and cycle detection.
• BFS — process level by level via a queue; the standard way to find shortest paths in an unweighted graph.

Why trees come first

Tree traversal is graph traversal with an implicit guarantee (no cycles, one path to any node) removed — so graph algorithms need explicit "visited" tracking that trees don't.