A graph is a non-linear data structure consisting of a set of vertices (also called nodes) and a set of edges that connect pairs of vertices. Among data structures, the graph is the most general way to represent relationships between items: road networks, social connections, web links, task dependencies and computer networks are all naturally modeled as graphs.
Formally, a graph is written as G = (V, E), where V is the vertex set and E the edge set. Edges can be directed or undirected, weighted or unweighted, and the structure may contain cycles, which distinguishes it from a tree, a restricted graph that is connected and has no cycles.
Vertices, edges and graph properties
Every graph is described by a few basic properties that determine which algorithms apply. Direction says whether an edge from A to B also implies an edge from B to A. Weight attaches a number such as distance, cost or capacity to each edge. Density compares the number of edges with the maximum possible, which is about V squared.
The degree of a vertex is the number of edges touching it; in directed graphs it splits into in-degree and out-degree. A path is a sequence of connected vertices, a cycle is a path that returns to its start, and a graph is connected when a path exists between every pair of vertices.
| Graph kind | Defining property | Typical example |
|---|---|---|
| Undirected | Edges have no direction | Friendship network |
| Directed (digraph) | Edges point one way | Web page links |
| Weighted | Edges carry numeric values | Road map with distances |
| Directed acyclic graph (DAG) | Directed with no cycles | Build or task dependencies |
| Bipartite | Two vertex groups, edges only between them | Users and products they bought |
| Tree | Connected and acyclic | File system hierarchy |
How graphs are stored in memory
A graph has no single built-in layout, so programs choose a representation that fits the graph’s density and the operations they perform most often. The two classic options are the adjacency list and the adjacency matrix, with the edge list used for simple storage and some algorithms.
An adjacency list stores, for each vertex, a list or dynamic array of its neighbors, often inside a hash table keyed by vertex. An adjacency matrix is a V by V array in which cell (i, j) records whether an edge exists or holds its weight. Large read-heavy graphs often use the compact compressed sparse row (CSR) format.
| Representation | Memory | Edge lookup | List neighbors | Best for |
|---|---|---|---|---|
| Adjacency list | O(V + E) | O(degree) | O(degree) | Sparse graphs, most applications |
| Adjacency matrix | O(V²) | O(1) | O(V) | Dense graphs, small V |
| Edge list | O(E) | O(E) | O(E) | Input files, Kruskal’s algorithm |
| Compressed sparse row | O(V + E), compact | O(log degree) if sorted | O(degree) | Very large static graphs |
Real-world graphs are usually sparse: a social network with millions of users has far fewer edges than V squared. For such graphs, an adjacency matrix would waste most of its memory, so the adjacency list is the default choice.
Core graph algorithms
Most graph processing builds on two traversal strategies. Breadth-first search (BFS) explores vertices level by level using a queue and finds shortest paths in unweighted graphs. Depth-first search (DFS) follows one branch as far as possible using a stack or recursion, and underlies cycle detection, topological sorting and finding connected components.
| Algorithm | Problem solved | Time complexity | Key requirement |
|---|---|---|---|
| Breadth-first search | Shortest path by edge count | O(V + E) | Unweighted edges |
| Depth-first search | Traversal, cycles, components | O(V + E) | None |
| Dijkstra’s algorithm | Shortest weighted paths | O((V + E) log V) with a binary heap | Non-negative weights |
| Bellman-Ford | Shortest paths with negative weights | O(V × E) | No negative cycles |
| Topological sort | Valid order of dependencies | O(V + E) | Directed acyclic graph |
| Kruskal or Prim | Minimum spanning tree | O(E log V) | Undirected weighted graph |
Dijkstra’s algorithm relies on a priority queue, typically a binary heap, to pick the closest unvisited vertex. Navigation systems add heuristics through A* search, which explores fewer vertices when a good distance estimate is available.
Graph compared with tree, list and hash table
The graph generalizes several simpler data structures. A linked list is a graph in which every vertex has at most one successor, and a tree is a connected acyclic graph with a single path between any two vertices. These restrictions make lists and trees easier to process, but they cannot express many-to-many relationships or cycles.
A hash table answers whether a key exists and what value it holds, but it does not model connections between keys. In practice the two are combined: a hash map from vertex identifiers to neighbor lists is one of the most common graph implementations in application code.
Practical pitfalls when working with graphs
Graph code fails in characteristic ways, mostly because cycles and size are underestimated. Forgetting a visited set in a traversal makes it loop forever on any cycle, and recursive DFS can overflow the call stack on graphs with long paths of hundreds of thousands of vertices.
| Symptom | Cause | Remedy |
|---|---|---|
| Infinite traversal | No visited tracking on cyclic graph | Mark vertices when first discovered |
| Stack overflow | Deep recursive DFS | Use an explicit stack |
| Wrong shortest paths | Dijkstra with negative weights | Use Bellman-Ford |
| Memory exhaustion | Adjacency matrix for a sparse graph | Switch to adjacency lists |
| Duplicate edges | Undirected edge stored inconsistently | Insert both directions in one function |
When data is mainly about relationships and queries span many hops, a dedicated graph database may serve better than hand-written structures, but in-memory graphs remain the right tool for algorithms inside an application.
Put simply
Picture a subway map. The stations are dots and the tracks are lines joining them. A graph is that idea turned into data: things are dots, and connections between them are lines.
Some lines go both ways, like a friendship. Others go one way, like following someone online. Lines can also carry numbers, like travel time between stations. With this picture stored in a computer, a program can answer questions such as what is the quickest way from here to there.
In practice
A logistics company plans daily delivery routes across a city. The street network is loaded as a weighted directed graph with roughly 200,000 intersections as vertices and 500,000 street segments as edges, with each edge weighted by expected travel time and one-way streets stored in a single direction.
The routing service stores the graph as adjacency lists and runs Dijkstra’s algorithm with a binary heap, switching to A* search when an exact destination is known. Travel-time weights are updated every few minutes from traffic data. Each route query explores only part of the graph and returns in a fraction of a second, so dispatchers can re-plan routes during the day when a road closes.