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.

🌐
Graphs are everywhere
Social networks, maps, and dependency systems are all graphs

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

➡️
Direction matters
One-way streets vs two-way streets
  • 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.

Interview signal:
When a problem says "find shortest path", check if the graph is weighted. Unweighted shortest path uses BFS. Weighted shortest path uses Dijkstra's algorithm or Bellman-Ford. This distinction is asked constantly at Google and Amazon.

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

0 1 2 3 4 5
Connected node Node 5 (degree 1 — leaf)

Edges: (0,1), (0,3), (0,4), (1,2), (1,3), (2,3), (4,5). Let's represent this same graph two ways:

Adjacency List
VertexNeighbours
0[1, 3, 4]
1[0, 2, 3]
2[1, 3]
3[0, 1, 2]
4[0, 5]
5[4]
Adjacency Matrix
012345
0010110
1101100
2010100
3111000
4100001
5000010
⚖
Trade-off
When to use each representation
  • 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.
Interview tip:
Always use an adjacency list unless the problem specifically requires O(1) edge queries. In 95% of graph interview problems, the adjacency list is the right choice. Mention the trade-off to show you've thought about it.

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.

build_graph.py Adjacency list from edge list — O(V + E)
Output
0: [1, 3, 4] 1: [0, 2, 3] 2: [1, 3] 3: [0, 1, 2] 4: [0, 5] 5: [4]

Using a plain dict (without defaultdict)

build_graph_plain.py Same result, no imports needed
Output
0: [1, 3, 4] 1: [0, 2, 3] 2: [1, 3] 3: [0, 1, 2] 4: [0, 5] 5: [4]

Adjacency matrix representation

adj_matrix.py O(V²) space — best for dense graphs
Output
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
Degree from adjacency list:
The degree of a vertex 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.

🏝️
Real-world analogy
Islands in an ocean — each island is a connected component

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.

connected_components.py DFS approach — O(V + E) time, O(V) space
Output
1 3 4

How it works

  1. Build the graph from the edge list as an adjacency list.
  2. Loop through all vertices from 0 to n-1.
  3. 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.
  4. DFS recursively visits every neighbour that hasn't been seen, marking each as visited. This floods the entire component.
Complexity:
Time is O(V + E) because DFS visits each vertex once and traverses each edge once. Space is O(V) for the visited set plus O(V) for the recursion stack in the worst case (a long chain graph).

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.

path_exists.py BFS approach — O(V + E) time, O(V) space
Output
True True True False

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).
Edge case:
Always check 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

Push yourself further
Challenge 1: Find all connected components (return groups)

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]].

Modify the connected components counter: instead of just incrementing a count, collect nodes during each DFS into a list. After DFS finishes for one component, append that list to your results. Don't forget isolated nodes — loop through all vertices 0 to n-1.
Challenge 2: Detect a cycle in an undirected graph

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.

During DFS, pass the parent of the current node. When visiting neighbours, if a neighbour is already visited AND it's not the parent, you've found a cycle. The parent check is critical: in an undirected graph, every edge creates a "back path" to the previous node, which is not a cycle.

Quiz

Question 1 of 5
What is the space complexity of an adjacency list for a graph with V vertices and E edges?
Question 2 of 5
In an undirected graph, if vertex A has degree 4, what does that mean?
Question 3 of 5
Which representation allows O(1) lookup to check if an edge exists between two specific vertices?
Question 4 of 5
You have a graph with 5 vertices and edges [(0,1), (2,3)]. How many connected components are there?
Question 5 of 5
What is the time complexity of BFS/DFS to find if a path exists between two vertices?
0
/5
Great work! You understand graph fundamentals.

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) AND graph[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.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →