What Is a Graph?
A graph is a collection of vertices (also called nodes) connected by edges. Unlike trees, graphs can have cycles, multiple paths between nodes, and nodes with no connections at all. Graphs are the most general-purpose data structure for modelling relationships.
On LinkedIn, each person is a vertex and each connection is an edge. Google Maps models intersections as vertices and roads as edges. Package managers like pip use graphs to track dependencies — package A depends on B, B depends on C. If you can draw dots connected by lines, you have a graph.
Key terminology
- Vertex (node): A single entity in the graph. Could be a person, city, web page, or any object.
- Edge: A connection between two vertices. Can be directed (one-way) or undirected (two-way).
- Degree: The number of edges connected to a vertex. In a directed graph, we distinguish in-degree (incoming edges) and out-degree (outgoing edges).
- Path: A sequence of vertices where each consecutive pair is connected by an edge.
- Cycle: A path that starts and ends at the same vertex.
- Connected component: A maximal group of vertices where every vertex can reach every other vertex through some path.
Directed vs Undirected Graphs
- Undirected graph: Edges have no direction. If A connects to B, then B connects to A. Think of a Facebook friendship — it goes both ways.
- Directed graph (digraph): Edges have direction. A → B does not imply B → A. Think of Twitter followers — you can follow someone without them following you back.
Weighted vs Unweighted
Edges can also carry weights — numerical values representing cost, distance, or capacity. A road map where edges represent distance in kilometres is a weighted graph. A social network where edges simply mean "connected" is unweighted.
Graph Representations
There are two standard ways to store a graph in memory: an adjacency list and an adjacency matrix. Let's see the same graph in all three views — visual, adjacency list, and adjacency matrix.
Sample Undirected Graph — 6 Vertices, 7 Edges
Edges: (0,1), (0,3), (0,4), (1,2), (1,3), (2,3), (4,5). Let's represent this same graph two ways:
| Vertex | Neighbours |
|---|---|
| 0 | [1, 3, 4] |
| 1 | [0, 2, 3] |
| 2 | [1, 3] |
| 3 | [0, 1, 2] |
| 4 | [0, 5] |
| 5 | [4] |
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 2 | 0 | 1 | 0 | 1 | 0 | 0 |
| 3 | 1 | 1 | 1 | 0 | 0 | 0 |
| 4 | 1 | 0 | 0 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 | 0 | 1 | 0 |
- Adjacency list — O(V + E) space: Best for sparse graphs (few edges relative to vertices). Most real-world graphs are sparse. Iterating over a node's neighbours is O(degree). This is the default choice in interviews.
- Adjacency matrix — O(V²) space: Best for dense graphs or when you need O(1) edge lookup ("is there an edge between u and v?"). Wastes memory on sparse graphs because most entries are 0.
Building a Graph in Python
The most Pythonic way to represent a graph is a dictionary of lists. Each key is a vertex, and its value is the list of neighbours. Let's build a graph from an edge list — a pattern you'll see in almost every graph interview question.
Using a plain dict (without defaultdict)
Adjacency matrix representation
v is simply len(graph[v]). For our graph, vertex 0 has degree 3 (connected to 1, 3, 4), while vertex 5 has degree 1 (connected only to 4).
Count Connected Components
A connected component is a group of vertices where you can reach any vertex from any other vertex in the group. Counting connected components is a classic interview problem — asked at Google, Amazon, and Microsoft. It's also the foundation for Union-Find.
Imagine vertices as pieces of land and edges as bridges. A connected component is an island — all land reachable by walking across bridges. Counting connected components means counting islands. This is literally LeetCode 200: Number of Islands, one of the most asked graph problems.
How it works
- Build the graph from the edge list as an adjacency list.
- Loop through all vertices from 0 to n-1.
- If a vertex hasn't been visited, it's the start of a new component. Run DFS from that vertex to mark all reachable vertices as visited. Increment the component count.
- DFS recursively visits every neighbour that hasn't been seen, marking each as visited. This floods the entire component.
Find If a Path Exists (BFS)
Given a graph and two vertices source and destination, determine if there's a path between them. This is LeetCode 1971 and a variation appears in almost every graph interview round.
BFS vs DFS for path finding
- BFS: Explores level by level using a queue. Finds the shortest path in an unweighted graph. Preferred when you need the minimum number of hops.
- DFS: Explores as deep as possible before backtracking using a stack (or recursion). Simpler to code recursively, but doesn't guarantee shortest path. Preferred when you just need to check existence.
- Both are O(V + E) for the basic existence check. The choice matters when you need shortest path (use BFS) or when the graph is very deep (use iterative DFS to avoid stack overflow).
source == destination first. This avoids unnecessary work and handles the trivial case where a node is always reachable from itself.
Try It Yourself
Determine if Two Nodes Are Connected
Given an edge list, implement a function to check if two nodes are connected. Use BFS or DFS — your choice. The starter code has the function signature and test cases ready.
Challenge
Given n vertices and an edge list, return a list of lists — each inner list contains the vertices in one connected component. For example, n=5, edges=[(0,1),(2,3)] should return [[0,1],[2,3],[4]].
Given an edge list, determine if the undirected graph contains a cycle. Return True if a cycle exists, False otherwise. Hint: This is asked by Amazon and Microsoft — a DFS variation where you track the parent node.
Quiz
Common Mistakes
- Forgetting to add both directions for undirected graphs. When building an adjacency list for an undirected graph, you must add
graph[u].append(v)ANDgraph[v].append(u). Missing the second line creates a directed graph by accident — one of the most common bugs in graph code. - Not tracking visited nodes. Without a visited set, BFS and DFS will loop forever on graphs with cycles. Always mark a node as visited the moment you add it to the queue (BFS) or the moment you enter the DFS call — not after you process it.
- Using an adjacency matrix for sparse graphs. A graph with 10,000 nodes and 20,000 edges needs a 10,000 x 10,000 matrix (100 million cells) but only 20,000 non-zero entries. Use an adjacency list instead — it uses O(V + E) space.
- Confusing vertex count with vertex labels. If a problem says "n = 5 vertices", the vertices might be 0-4 or they might be labelled with strings. Read the problem carefully and choose your data structure accordingly —
defaultdict(list)handles any hashable label. - Infinite recursion on large graphs. Python's default recursion limit is ~1000. For graphs with long chains (e.g., 10,000 nodes in a line), recursive DFS will hit a stack overflow. Use iterative DFS with an explicit stack, or call
sys.setrecursionlimit().
Key Takeaways
- Graphs = vertices + edges. They model any relationship: social networks, road maps, dependencies, web pages. Every connection problem is a graph problem.
- Adjacency list is the default choice. Use
defaultdict(list)or a plain dict. It's O(V + E) space and efficient for the sparse graphs you'll see in 95% of interviews. - Connected components via DFS: Loop through all vertices; for each unvisited vertex, run DFS to flood the component and increment the count. O(V + E) time.
- Path existence via BFS or DFS: Both are O(V + E). Use BFS when you also need shortest path in an unweighted graph. Always check source == destination first.
- Next up: BFS and DFS in depth. Graph fundamentals are the vocabulary. BFS and DFS are the verbs — the traversal algorithms that power almost every graph problem you'll face in interviews.
You've learned graph fundamentals.
Now build the career they unlock.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →