Introduction to Graphs
A social network, a road map, a course catalog, the web, your git history — they look like completely different problems. They’re all the same structure: nodes connected by edges. Master that one abstraction and a single algorithm suddenly answers “who’s the shortest chain of friends to this person?”, “what’s the fastest route?”, and “in what order can I take these courses?” — because the graph doesn’t care what the nodes mean.
A graph is a set of nodes (also called vertices) connected by edges. That’s it. Both definitions are deliberately vague — the meaning of nodes and edges depends entirely on what you’re modeling.
In a social network, nodes are people and edges are friendships. In a city map, nodes are intersections and edges are roads. In a course catalog, nodes are courses and edges are prerequisites. The graph algorithm doesn’t care.
Notation
The standard math notation:
G = (V, E) — a graph G is the pair of a vertex set V and an edge set E.
When we write n = |V| we mean “number of vertices” and m = |E| for “number of edges.” Complexity analyses use these letters constantly: O(V + E), O(V log V + E), and so on.
The four design choices
Every graph problem starts with four yes/no questions. The answers shape what algorithms you can use.
1. Directed or undirected?
- Undirected edges have no direction — if A is connected to B, then B is connected to A. Friendships, two-way streets, “X is similar to Y.”
- Directed edges (also called arcs) point one way — A → B does not mean B → A. Twitter follows, web hyperlinks, “A depends on B.”
2. Weighted or unweighted?
- Unweighted edges all count the same. “Find a path from A to B” means any path.
- Weighted edges carry a number — a cost, distance, capacity, probability. “Find the shortest path” usually means the cheapest weighted total.
3. Connected or disconnected?
- Connected — every node is reachable from every other (in undirected graphs).
- Disconnected — the graph splits into multiple connected components. You can’t get from one piece to another.
Most real-world graphs are almost connected with a few isolated bits. Most algorithm questions assume connected unless they specifically test for components.
4. Simple or multigraph?
- Simple graph — at most one edge between any pair of nodes, no self-loops (an edge from A to A).
- Multigraph — multiple edges between the same pair allowed; self-loops allowed.
99% of interview problems are simple graphs. Multigraphs come up in real-world routing (multiple flights between the same two cities) and some specialized algorithms.
Vocabulary you’ll meet again
The terms that show up in every graph algorithm. Learn these now and you won’t be lost later.
Degree
The degree of a node is the number of edges touching it. In a directed graph, we distinguish:
- In-degree — incoming edges
- Out-degree — outgoing edges
Path
A path is a sequence of nodes where each consecutive pair is connected by an edge. The length of a path is the number of edges (or sum of weights for weighted graphs).
A path that doesn’t repeat any node is a simple path — most algorithms only care about these.
Cycle
A cycle is a path that starts and ends at the same node, with all other nodes distinct. A graph with no cycles is acyclic.
A directed acyclic graph — DAG — is one of the most common shapes in real applications: build systems, course dependencies, lineage trees, version histories.
Connected component
In an undirected graph, a connected component is a maximal set of nodes that can all reach each other. A graph with one component is “connected”; with more, it’s “disconnected.”
In a directed graph there are two flavours: strongly connected (you can reach every node from every other, in both directions) and weakly connected (you can if you ignore edge directions).
Tree
A tree is a special graph: connected, undirected, no cycles. n nodes means exactly n-1 edges. You met trees on Day 6; we’ll re-meet them everywhere.
Bipartite
A graph is bipartite if its nodes can be split into two groups such that every edge goes between groups, never within. Job applicants and jobs. Students and courses. Boys and girls at a dance. Bipartite structure unlocks faster algorithms (maximum matching, Hopcroft-Karp).
A worked example: read this graph
Full breakdown:
- 6 nodes, 5 edges. (Count the lines.)
- Node A has degree 2 (neighbours B and C). Node C has degree 2. Node B has degree 3 (A, C, D).
- It’s disconnected —
{A, B, C, D}is one component,{E, F}is another. - It has a cycle: A → B → C → A.
- It’s undirected (no arrows shown).
That’s basically all the vocabulary you need to read any graph problem statement.
Quick check
You can now read any graph and name its properties. Next: representation — how to actually store a graph in code (adjacency list vs matrix), and why that choice quietly sets the complexity of every algorithm you’ll run on it.