What is a Graph?
Data Structures·6 min read·code in python
A graph is a data structure that models relationships as a set of vertices (nodes) connected by edges (links). Edges can be directed or undirected, weighted or unweighted. Graphs represent anything with connections, road maps, social networks, web pages, or task dependencies, and are usually stored as an adjacency list or adjacency matrix.
The idea: nodes and the connections between them
Think of a graph as a map of dots and lines. Each dot is a vertex: a person, a city, a web page, a task. Each line is an edge: a friendship, a road, a hyperlink, or a "must happen before" relationship. That is the whole model. Trees and linked lists are really just graphs with extra rules; a plain graph makes no promise about shape, so a vertex can connect to none, one, or thousands of others, and cycles are allowed.
The power is that once you notice something is "items plus relationships," a whole library of graph algorithms opens up: shortest paths, reachability, cycle detection, ordering. Recognizing the graph hiding inside a word problem is often the hardest and most valuable step, and it gets much easier once you have watched a traversal move across the nodes a few times.
Directed, undirected, and weighted edges
Edges carry meaning through two properties. Direction: an undirected edge is mutual (a Facebook friendship), while a directed edge goes one way (a Twitter follow, or a course prerequisite). Weight: an unweighted edge just says "connected," while a weighted edge attaches a number, distance, cost, time, or capacity. A road map is a weighted undirected graph; a build system is a directed graph whose edges mean "depends on."
These choices decide which algorithms apply. Dijkstra's needs non-negative weights, topological sort needs a directed acyclic graph (DAG), and detecting a cycle in a directed graph differs from doing it in an undirected one. Naming the edge type first is how you pick the right tool.
Adjacency list vs adjacency matrix
You mainly store a graph two ways. An adjacency list keeps, for each vertex, a list of its neighbors, compact when edges are few (a sparse graph), which describes most real-world data. An adjacency matrix is a V×V grid where cell [u][v] marks whether an edge exists, giving O(1) edge lookups and clean math, but costing O(V²) space even when the graph is nearly empty.
Rule of thumb: default to an adjacency list. It uses O(V + E) space and lets you iterate a vertex's neighbors in time proportional to how many there are, which is exactly what BFS and DFS need. Reach for a matrix when the graph is dense, very small, or when you need constant-time "is there an edge?" checks or matrix operations.
The code
from collections import defaultdict, deque
class Graph:
def __init__(self, directed=False):
self.adj = defaultdict(list)
self.directed = directed
def add_edge(self, u, v):
self.adj[u].append(v)
if not self.directed:
self.adj[v].append(u)
def bfs(self, start):
seen, order, q = {start}, [], deque([start])
while q:
node = q.popleft()
order.append(node)
for nxt in self.adj[node]:
if nxt not in seen:
seen.add(nxt)
q.append(nxt)
return orderRun it in the browser IDE, free on the platform. Open the IDE
Complexity
| Time | Traversal (BFS/DFS): O(V + E). Edge lookup: O(degree) with an adjacency list, O(1) with a matrix. |
|---|---|
| Space | O(V + E) for an adjacency list; O(V²) for an adjacency matrix. |
V = vertices, E = edges. Adjacency lists win on sparse graphs (E far below V²), which covers most real data; matrices win on dense graphs and constant-time edge checks.
Watch it run
Reading the steps is one thing. Watching any of these move on your own input, one step at a time, is where the picture sticks.
When to use it
- Modeling anything where items connect: social graphs, road and transit maps, computer networks, or web-page links.
- Finding shortest or cheapest paths between points (GPS routing, network latency) using BFS, Dijkstra, or A*.
- Ordering tasks with dependencies, build systems, course prerequisites, package installs, via topological sort on a DAG.
- Answering reachability and connectivity questions: can A reach B, how many connected components exist, is there a cycle?
Watch out for
- Using an adjacency matrix for a large sparse graph, burning O(V²) memory when an adjacency list would use only O(V + E).
- Forgetting to track visited nodes during traversal, so cycles cause infinite loops or exponential repeated work.
- Mixing up directed and undirected edges, adding an edge only one way when the relationship is mutual, or both ways when it isn't.
Graph: questions we get
Is graph a hard topic to learn?
The core idea, dots connected by lines, is simple, and most people grasp it quickly. The real difficulty is recognizing when a problem is secretly a graph and remembering which traversal fits. It tends to click much faster when you watch a traversal animate node by node instead of tracing it by hand on paper.
When should I use an adjacency list vs an adjacency matrix?
Default to an adjacency list. It uses O(V + E) space and suits the sparse graphs found in most real data. Use a matrix when the graph is dense, very small, or when you need constant-time "is there an edge between u and v?" checks or matrix-style operations.
What is the difference between a graph and a tree?
A tree is a special kind of graph: connected, undirected, with no cycles and exactly V − 1 edges. A general graph has no such rules. It can contain cycles, be disconnected, and let any node have any number of connections. Every tree is a graph, but not every graph is a tree.
What is the time complexity of traversing a graph?
Visiting every vertex and edge once with BFS or DFS is O(V + E) using an adjacency list, because you touch each vertex once and scan each edge once. With an adjacency matrix it becomes O(V²), since checking one vertex's neighbors means scanning an entire row.
Related concepts
Reading is the easy part. In a batch you build it, say it out loud in a scored mock round and hear what an interviewer would think.
Talk to mentor