Graphs
What Is a Graph?
A graph is a data structure made of vertices (also called nodes) connected by edges. Unlike a tree, which forces a single strict hierarchy flowing down from one root, a graph places no such restriction on how nodes connect — any vertex can connect to any number of other vertices, in any pattern, including connections that loop back on themselves. That flexibility is exactly what makes graphs the natural way to model networks: cities linked by roads, people linked by friendships, web pages linked by hyperlinks, computers linked by cables.
A --- B
| |
C --- D --- E
In this graph, A, B, C, D, and E are vertices, and each line between them is an edge. D connects to three other vertices; A connects to two. There is no root and no fixed direction to read the diagram in — it is simply a web of relationships.
Directed vs Undirected
An undirected graph has edges that work both ways, like the example above — if A connects to C, you can travel from A to C and from C to A. A directed graph (sometimes called a digraph) has edges that only go one way, drawn with an arrow: a one-way street, a Twitter/X "follow," or a prerequisite that must be completed before a later course. Following a directed edge backward is not automatically possible.
Weighted vs Unweighted
An unweighted graph treats every edge as equal — it exists or it doesn't. A weighted graph attaches a number to each edge, representing a cost, distance, time, or capacity. A road network is naturally weighted: the edge between two cities might carry the driving distance or travel time. Weighted graphs matter enormously for real routing problems, where the goal is not just a path but the cheapest path.
Other Key Vocabulary
- Adjacent vertices are directly connected by a single edge.
- A path is a sequence of edges connecting one vertex to another.
- A cycle is a path that starts and ends at the same vertex without repeating an edge — a graph containing one is called cyclic; a graph with none is acyclic.
- The degree of a vertex is the number of edges connected to it (in a directed graph, this splits into in-degree and out-degree).
- A graph is connected if there is some path between every pair of vertices; otherwise it splits into separate pieces.
Storing a Graph: Two Representations
Because a graph's shape is so flexible, there is no single obvious way to store one in memory — two representations dominate, and the right choice depends on the graph's shape.
An adjacency matrix is a grid with one row and one column per vertex. Cell [i][j] holds a 1 (or an edge weight) if vertex i connects to vertex j, and a 0 otherwise. Checking whether two specific vertices are connected is instant — just look up one cell — but the matrix always needs space for every possible pair of vertices, whether or not that edge exists.
An adjacency list instead gives each vertex a list of only the vertices it actually connects to. This uses far less memory when a graph is sparse (few edges relative to the number of possible pairs, like most real-world networks), because it never stores the near-total sea of "no edge here" that a matrix does for a sparse graph. The trade-off is that checking one specific edge means scanning a list rather than jumping to one cell.
Traversing a Graph: BFS and DFS
Visiting every vertex in a graph is called traversal, and — as with trees — there are two fundamental strategies.
Breadth-first search (BFS) explores outward one full layer at a time: it visits the start vertex, then every vertex directly adjacent to it, then every vertex adjacent to those, and so on. It uses a queue to keep track of which vertex to expand next, always processing the vertex that has been waiting longest. Because BFS finishes an entire layer before starting the next, it is the standard way to find the shortest path between two vertices in an unweighted graph, measured simply by number of edges.
Depth-first search (DFS) instead commits to a single path, following edges as far as possible before backtracking to try another branch — much like exploring a maze by always taking the next unexplored turn and only reversing when you hit a dead end. DFS is typically implemented with a stack, either explicitly or implicitly through recursion. It's a natural fit for problems like detecting whether a graph contains a cycle, or exploring every possible path.
Graph: Start: A
A
/ \
B C
| |
D E
BFS order: A B C D E (layer by layer)
DFS order: A B D C E (down one branch, then back up)
Where Graphs Show Up
Graphs are everywhere once you start looking. GPS and mapping apps model road junctions as vertices and roads as weighted edges, then use graph algorithms to find the fastest route. Social networks model people as vertices and friendships or follows as edges. The web itself is a directed graph, with pages as vertices and hyperlinks as directed edges — the same structure early search engines exploited to rank pages by how many other pages linked to them. Computer networks model devices as vertices and connections as edges to route data efficiently. Even a flowchart or a state diagram in a video game is a small directed graph, where vertices are states and edges are the transitions between them.
Key Words
- Vertex (node) — a single point in a graph
- Edge — a connection between two vertices
- Directed / undirected — whether edges have a one-way or two-way direction
- Weighted / unweighted — whether edges carry a cost or are simply present or absent
- Adjacency matrix — a grid representation storing every possible vertex pair
- Adjacency list — a representation storing only the edges that actually exist
- BFS — breadth-first search; explores layer by layer using a queue
- DFS — depth-first search; follows one path as far as possible using a stack or recursion
Questions & comments
Comments are public and are checked before they appear. Please don’t post your full name, email, phone number, school, or anything else that identifies you. How we use this.
Loading comments…