Graphs
dsa.fetehadin.com7.1 Graph Terminology
Vertices and edges, adjacency, degree, paths, cycles, connected graphs, weighted graphs, and how a tree is a special graph.
| max edges, undirected | V(V − 1)/2 |
| max edges, directed | V(V − 1) |
| sum of all degrees | 2E (each edge counted at both ends) |
| Space | Depends on the representation (next topic) |
- ✗Counting path length in vertices instead of edges.
- ✗Saying every graph is connected.
- ✗Forgetting that a cycle must not reuse an edge.
7.2 Adjacency Matrix & Adjacency List
Two ways to store a graph in memory, what each costs, and when to choose which.
| space | matrix O(V²) · list O(V + E) |
| is there an edge u–v? | matrix O(1) · list O(deg u) |
| visit all neighbours of u | matrix O(V) · list O(deg u) |
| add an edge | matrix O(1) · list O(1) |
- ✗Setting only
m[u][v]for an undirected edge. Setm[v][u]too. - ✗Saying the list is always better. Edge lookup is O(1) only in the matrix.
- ✗Forgetting that an undirected edge appears twice in the list.
7.3 Directed Graphs
One-way edges, in-degree and out-degree, directed paths and cycles, and how the matrix and list change.
| out-degree of u | list O(1) (size of adj[u]) · matrix O(V) (row sum) |
| in-degree of u | list O(V + E) · matrix O(V) (column sum) |
| space | matrix O(V²) · list O(V + E) |
- ✗Adding both
m[u][v]andm[v][u]for a directed edge. - ✗Following an arrow backwards when tracing a path.
- ✗Mixing up in-degree (arrows coming in) and out-degree (arrows going out).
7.4 BFS & DFS
Breadth-first search with a queue, depth-first search with recursion or a stack, the visited array, and O(V + E).
| BFS / DFS with adjacency list | O(V + E) |
| BFS / DFS with adjacency matrix | O(V²) |
| Space | O(V) for visited plus the queue or stack |
- ✗No visited array, so the search loops forever around a cycle.
- ✗In BFS, marking a vertex visited when it is dequeued instead of enqueued (it can be enqueued twice).
- ✗Visiting neighbours in a different order from the one the question uses (usually ascending).
- Graph:
- G = (V, E): a set of vertices and a set of edges between them.
- Degree:
- Number of edges at a vertex. In a digraph, split into in-degree and out-degree.
- Path / cycle:
- A sequence of vertices joined by edges / a path that returns to its start.
- Connected graph:
- There is a path between every pair of vertices.
- Adjacency matrix:
- V×V table where m[u][v] = 1 (or the weight) if there is an edge u→v. O(V²) space.
- Adjacency list:
- For each vertex, a list of its neighbours. O(V + E) space.
- Directed graph (digraph):
- A graph whose edges are one-way arrows.
- DAG:
- Directed acyclic graph: a digraph with no directed cycles.
- BFS:
- Breadth-first search: explore neighbours in waves using a queue. Finds fewest-edge paths.
- DFS:
- Depth-first search: go as deep as possible, then backtrack, using recursion or a stack.