A graph is a collection of vertices (also called nodes) and edges (connections between them).
Unlike trees, a graph has no root, no parent-child hierarchy, and no restriction on how vertices connect to each other.
This generality makes graphs the most powerful and widely used data structure in computer science —
every network, map, social platform, web crawler, and recommendation engine is built on graph algorithms.
Foundations
Graph Terminology
A graph G is defined as G = (V, E) where V is the set of vertices and E is the set of edges. Each edge connects two vertices. Understanding the vocabulary is essential before studying traversal algorithms.
⭕
Vertex (Node)
A fundamental unit of the graph. Represents an entity — a city, a person, a web page, a router. In the diagram above, A, B, C, D, and E are vertices.
➖
Edge
A connection between two vertices. An edge (u, v) connects vertex u to vertex v. Edges can be unweighted (just a connection) or weighted (a numerical cost, distance, or capacity).
🔢
Degree
The number of edges connected to a vertex. In an undirected graph, vertex A has degree 2 (connected to B and D). In a directed graph, in-degree and out-degree are counted separately.
🛤️
Path
A sequence of vertices where each consecutive pair is connected by an edge. A simple path visits no vertex more than once. Path length is the number of edges (or sum of weights for weighted paths).
🔄
Cycle
A path that starts and ends at the same vertex. Graphs without cycles are called acyclic. A directed acyclic graph (DAG) is fundamental for scheduling and dependency resolution.
🌐
Connected Graph
An undirected graph is connected if there is a path between every pair of vertices. A disconnected graph has isolated components with no edges between them.
Types of Graphs
Directed · Undirected · Weighted · Cyclic
↔️
Undirected Graph
Edges have no direction — if A is connected to B, then B is also connected to A. The connection is mutual and symmetric. Represented as {A, B}. Examples: friendship networks, road maps (two-way roads), collaboration networks.
➡️
Directed Graph (Digraph)
Edges have a direction — (A → B) does not imply (B → A). The connection is one-way. Represented as (A, B). Examples: web pages with hyperlinks, Twitter follows, dependency graphs, city road networks with one-way streets.
⚖️
Weighted Graph
Each edge carries a numerical weight — a cost, distance, capacity, or time. Algorithms like Dijkstra's shortest path and Prim's minimum spanning tree operate on weighted graphs. Most real-world graphs are weighted.
🌲
Tree as a Special Graph
A tree is a connected, undirected, acyclic graph with exactly n−1 edges for n vertices. Every tree is a graph, but not every graph is a tree. Removing the "no cycle" restriction makes a tree a general graph.
Storage
Graph Representations
A graph can be stored in two primary ways. The choice determines the time and space complexity of every algorithm that operates on it.
🗃️
Adjacency Matrix
A 2D array of size V×V where matrix[i][j] = 1 (or weight) if there is an edge from i to j, else 0.
Space: O(V²) — wasteful for sparse graphs Edge lookup: O(1) — check matrix[i][j] Find all neighbours: O(V) — scan row i Best when: dense graphs (many edges), frequent edge-existence queries
🔗
Adjacency List
An array of V linked lists. List[i] contains all vertices adjacent to vertex i.
Space: O(V + E) — efficient for sparse graphs Edge lookup: O(degree(v)) — scan the list Find all neighbours: O(degree(v)) — iterate the list Best when: sparse graphs (few edges), traversal-heavy algorithms (BFS, DFS)
Most real-world graphs are sparse. A social network with 1 billion users and 100 billion friendships has an average degree of 100 — each user is connected to 100 others out of 1 billion possible. An adjacency matrix would need 10¹⁸ cells. An adjacency list needs only 10¹¹ entries. Adjacency lists are almost always the right choice.
Traversal Algorithms
BFS and DFS — Two Ways to Explore a Graph
Graph traversal means visiting every reachable vertex from a given source exactly once. Two fundamentally different strategies exist, each suited to different problems.
🌊
BFS — Breadth-First Search
Uses a Queue (FIFO). Visits all vertices at distance 1 before any at distance 2, then all at distance 2 before distance 3, and so on. Explores level by level, spreading outward like a wave.
Guarantees: shortest path (fewest edges) in an unweighted graph Data structure: Queue Complexity: O(V + E)
🔍
DFS — Depth-First Search
Uses a Stack (LIFO) — either an explicit stack or the implicit call stack via recursion. Goes as deep as possible along one path before backtracking and trying another. Explores one branch fully before moving to siblings.
Guarantees: visits all reachable vertices; finds cycles Data structure: Stack (or recursion) Complexity: O(V + E)
BFS from vertex A — visits level by level using a Queue
Start:A→ Queue: [A]
Dequeue A, visit. Enqueue neighbours B, D:A ✓Queue: [B, D]
Dequeue D, visit. No new neighbours:D ✓Queue: [C, E]
Dequeue C, E → visit both:C ✓E ✓Queue: [] Done
BFS order: A → B → D → C → E | Shortest path from A to E: A-B-E (2 edges)
DFS from vertex A — goes deep first using a Stack
Start:A→ Stack: [A]
Pop A, visit. Push neighbours D, B:A ✓Stack: [D, B]
Pop B, visit. Push C, E:B ✓Stack: [D, C, E]
Pop E, visit. Pop C, visit:E ✓C ✓Stack: [D]
Pop D, visit. Stack empty:D ✓Done
DFS order: A → B → E → C → D | All 5 vertices visited
// BFS pseudocodefunction BFS(graph, source):
queue.enqueue(source)
visited[source] = truewhile queue not empty:
node = queue.dequeue()
process(node)
for each neighbour of node:
if not visited[neighbour]:
visited[neighbour] = true
queue.enqueue(neighbour)
// DFS pseudocode (recursive)function DFS(node, visited):
visited[node] = true
process(node)
for each neighbour of node:
if not visited[neighbour]:
DFS(neighbour, visited)
Performance
Time and Space Complexity
Operation
Adjacency Matrix
Adjacency List
Notes
Add vertex
O(V²)
O(1)
Matrix must be resized
Add edge
O(1)
O(1)
Set matrix[u][v] or append to list
Check edge (u,v)
O(1)
O(degree(u))
Matrix wins for random edge queries
Find all neighbours of u
O(V)
O(degree(u))
List wins for traversal
BFS traversal
O(V²)
O(V + E)
Matrix scans full row per vertex
DFS traversal
O(V²)
O(V + E)
Same reason as BFS
Space
O(V²)
O(V + E)
List is far smaller for sparse graphs
O(V + E) explained: BFS and DFS visit each vertex once (O(V)) and each edge once or twice (O(E)). The total is O(V + E). For a sparse graph where E ≈ V, this is essentially O(V). For a dense graph where E ≈ V², this approaches O(V²) — which is why dense graphs sometimes benefit from adjacency matrices.
Applications
Where Graphs Are Used
🗺️
Shortest Path — GPS Navigation
Road networks are weighted directed graphs — intersections are vertices, roads are edges with weights representing distance or travel time. Dijkstra's algorithm finds the shortest path between two vertices in O((V + E) log V) time. Every GPS navigation system runs a variant of this algorithm.
👥
Social Networks
Friendship networks (Facebook, LinkedIn) are undirected graphs. Follow networks (Twitter, Instagram) are directed graphs. BFS from a user finds all users within k degrees of separation. Graph clustering algorithms detect communities. PageRank (used by Google) computes vertex importance in a directed graph.
📦
Dependency Resolution
Package managers (npm, pip, Maven) represent software dependencies as a directed acyclic graph (DAG). Package A depends on B and C; B depends on D. Topological sorting of the DAG gives the correct installation order — every dependency is installed before the package that requires it.
🌐
Web Crawling and Indexing
The World Wide Web is a directed graph — web pages are vertices and hyperlinks are directed edges. Search engine crawlers use BFS to discover pages systematically: start from a seed URL, visit all linked pages, enqueue their links, and repeat. BFS ensures pages are discovered in order of their distance from the seed.
Interactive Learning
Graph Quest — Build and Traverse
Click on the canvas to add vertices, then click two vertices to add an edge between them. Select BFS or DFS and choose a starting vertex to see the traversal animate node by node, with a visit log showing the order of discovery.