A graph is a structure made of nodes, also called vertices, and the connections between them, called edges — nothing more prescriptive than that. Where a tree forces a strict parent-child hierarchy, a graph allows any node to connect to any other node, including cycles back to itself. That flexibility is exactly why graphs model so much of the real world: social networks, road maps, dependency chains, and web links are all naturally graphs, not trees.
What changed in 2026
- Graph structures kept expanding into AI infrastructure. Knowledge graphs, dependency graphs for agent tool-calling, and graph-based retrieval sit alongside the classical uses in networking and mapping.
- Graph databases matured into a mainstream storage choice for relationship-heavy data, rather than a niche alternative to relational databases, specifically because traversing relationships in SQL through joins gets expensive fast.
- GPU-accelerated graph algorithms became more accessible, speeding up large-scale traversal and shortest-path computation for graphs with billions of edges.
Core vocabulary
- Vertex, or node: a single entity — a person, a city, a web page.
- Edge: a connection between two vertices, optionally carrying a weight, a cost or distance.
- Directed vs undirected: a directed edge only goes one way, such as one account following another; an undirected edge goes both ways, such as a friendship.
- Weighted vs unweighted: a weighted edge carries a cost, like road distance or latency; an unweighted edge only represents connected or not.
- Cycle: a path that returns to its starting vertex — trees cannot have cycles, graphs can.
Representing a graph in code
Adjacency list (most common):
A: [B, C]
B: [A, D]
C: [A]
D: [B]
Adjacency matrix:
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 0
D 0 1 0 0
Adjacency list vs adjacency matrix
| Property |
Adjacency list |
Adjacency matrix |
| Space |
O(V + E) |
O(V²) |
| Check if an edge exists |
O(degree of vertex) |
O(1) |
| Iterate all neighbors |
O(degree of vertex) |
O(V) |
| Best for |
Sparse graphs, most real graphs |
Dense graphs, or frequent O(1) edge checks |
Most real-world graphs are sparse — a social network with a million users does not have close to a trillion connections — so adjacency lists dominate in practice.
What gets done with a graph once it exists
Storing the graph is the easy part; the algorithms are where the value is. Depth-first and breadth-first search traverse a graph to find reachability or shortest paths in unweighted graphs. Dijkstra's algorithm finds shortest paths when edges carry non-negative weights. Topological sort orders a directed acyclic graph so every edge points forward — the basis of build systems and task scheduling. Union-Find, or disjoint set, tracks connected components efficiently as edges are added.
Common pitfalls
Modeling a tree problem as a graph, or vice versa, without noticing the difference. A tree is a graph with no cycles and exactly one path between any two nodes — algorithms that assume that, like naive recursion without a visited set, will loop forever on a graph with cycles.
Forgetting a visited set during traversal. Because graphs allow cycles, traversing without tracking visited nodes causes infinite loops — trees are more forgiving here since acyclic structure prevents revisiting.
Choosing an adjacency matrix for a sparse graph. The O(V²) memory cost becomes untenable fast; a graph with 100,000 vertices and an average of five connections each wastes almost all of a 100,000-by-100,000 matrix on zeros.
FAQ
Is a tree a type of graph?
Yes — a tree is a connected, acyclic graph with exactly one path between any two nodes. Every tree is a graph, but not every graph is a tree.
What is the difference between a graph and a network?
None, formally — network is typically the applied term, such as social network or computer network, for what is structurally a graph. The math and algorithms are identical.
How should someone choose between an adjacency list and an adjacency matrix?
Default to an adjacency list unless the graph is dense, with edges close to V², or O(1) edge-existence checks are needed frequently enough to justify the memory cost.
Is a dedicated graph database required to work with graphs?
No — an adjacency list in a regular database or in memory handles most use cases. A dedicated graph database earns its place when relationship traversal several hops deep is the dominant query pattern and SQL joins are becoming the bottleneck.
Where to go next