adjacency list vs adjacency matrix
Before you can run any graph algorithm you have to write the graph down somewhere, and there are two natural ways to do it. Picture a small social network of n people. One way is a giant n-by-n grid where the cell in row u, column v is 1 if u and v are friends and 0 otherwise — that is the adjacency matrix. The other way is to give each person a little list of exactly the friends they have — that is the adjacency list. Both record the same friendships; they just differ in what they make fast and what they make wasteful.
Precisely: the adjacency matrix A is an n-by-n array with A[u][v] = 1 when there is an edge from u to v (and a weight there instead of 1 if the graph is weighted). It uses Theta(n^2) space no matter how few edges there are, but it answers 'is u adjacent to v?' in O(1) by a single lookup. The adjacency list stores, for each vertex u, a list of its neighbours; it uses Theta(n + m) space where m is the number of edges, and to scan all neighbours of u costs time proportional to u's degree. The trade-off is sharpest on the two operations graph search needs most: BFS and DFS visit every vertex and walk along every edge once, so over the whole run a list lets them finish in O(n + m), while a matrix forces them to scan a full row of length n per vertex, giving O(n^2) even on a sparse graph.
Which to pick comes down to density. A graph is sparse when m is much smaller than n^2 (think road maps or social graphs, where each vertex touches only a handful of others); there the list wins decisively on both space and the time of a full traversal. A graph is dense when m is close to n^2, or when you constantly ask single-edge existence questions or do matrix-style math (like raising A to a power to count walks); there the matrix's O(1) lookup and compact n^2 footprint pay off. Most real-world graphs are sparse, which is why the adjacency list is the default representation behind nearly every algorithm in this field.
A graph on 5 vertices with edges {1-2, 2-3, 3-1}. As a matrix it is a 5x5 grid (25 cells) with six 1s. As a list it is: 1 -> [2,3], 2 -> [1,3], 3 -> [1,2], 4 -> [], 5 -> [] — just six neighbour entries. Checking 'is 1 adjacent to 4?' is one matrix lookup, or a short scan of vertex 1's list.
Same graph, two layouts: the matrix always costs 25 cells; the list costs only as much as the edges actually present.
Saying an algorithm is O(n + m) silently assumes an adjacency list; the very same code on an adjacency matrix is O(n^2). Always state the representation when you quote a graph running time.