What is a Graph

A graph is a collection of nodes (also called vertices) connected by edges. Unlike trees, graphs have no root, no hierarchy, and no restriction on connections — any node can link to any other node, including itself. This makes graphs the most general-purpose data structure for modeling relationships.

How it works

A graph is defined by two sets: nodes and edges. An edge connects two nodes and can be directed (one-way, like a web link) or undirected (two-way, like a friendship). Edges can also carry weights (numeric values representing distance, cost, or capacity).

Undirected:    A --- B --- C        Directed:    A → B → C
               |         |                        ↑       ↓
               D --- E                             D ← E

Two common representations in code:

• Adjacency list — each node stores a list of its neighbors. Space-efficient for sparse graphs (few edges). Most real-world graphs are sparse.
• Adjacency matrix — a 2D array where matrix[i][j] = 1 if an edge exists between nodes i and j. Fast edge lookup but uses O(n^2) space.

Traversal algorithms explore the graph systematically:

• Breadth-first search (BFS) — explores all neighbors before moving deeper, using a queue. Finds shortest paths in unweighted graphs.
• Depth-first search (DFS) — explores as deep as possible before backtracking, using a stack. Useful for cycle detection, topological sorting, and connected components.

Trees are a special case of graphs — connected, acyclic, undirected graphs. A binary search tree is a graph with ordering constraints and at most two edges per node.

Why it matters

Graphs model problems that no other data structure can. The internet is a graph of routers. A dependency manager resolves a directed acyclic graph of packages. Social networks are graphs of users. Map routing is shortest-path through a weighted graph. In AI, approximate nearest neighbor search uses graph structures (HNSW) to find similar vectors.

See How Graphs Work for traversal algorithms and real-world applications.