A graph is a data structure made of vertices (nodes) and edges, the links between them. It can be directed or undirected, weighted or unweighted, connected or disconnected, cyclic or acyclic. Store it as an adjacency list or matrix and explore it with breadth-first search (BFS) or depth-first search (DFS), both O(V + E).
Graphs appear in DSA (data structures and algorithms) courses, college exams and most coding interviews. This page covers the terms people search for (graph in DSA, disconnected graph, cyclic graph, acyclic graph) and then the code.
Every code block was run on Python 3.9 and Node 24 on 11 November 2026 and the output shown is the real output. Complexity figures were checked against Wikipedia's graph, BFS and DFS pages on the same date.
- 1Model itdecide what the vertices and edges are
- 2Store itadjacency list in most cases
- 3Traverse itBFS for nearest first, DFS for deep first
- 4Answer itpath, cycle, components or order
What a graph is, and the types of graph
A graph is a set of vertices (also called nodes) joined by edges, written G = (V, E). Cities joined by roads, people joined by friendships and web pages joined by links are all graphs: the cities, people and pages are vertices, and the roads, friendships and links are edges.
| Term | Meaning | Example |
|---|---|---|
| Vertex (node) | One point in the graph | A city |
| Edge | A link between two vertices | A road |
| Degree | Number of edges at a vertex (in-degree and out-degree in a directed graph) | A person with 120 friends has degree 120 |
| Path | A sequence of vertices where each consecutive pair is joined by an edge | Delhi, Jaipur, Ahmedabad |
| Cycle | A path that ends where it started | A, B, D, C, back to A |
| Weight | A number stored on an edge | Distance in km |
A tree is a special graph: connected, with no cycles. Most of what follows also applies to trees.
Types of graphs
| Type | What it means | Real example |
|---|---|---|
| Undirected | An edge works both ways | Facebook-style friendship |
| Directed (digraph) | An edge has a direction: A to B is not B to A | Follows on Instagram, one-way streets |
| Weighted or unweighted | Weighted edges carry a cost. In an unweighted graph every edge counts the same, so length means number of edges | Road length, ticket price, hops between people |
| Connected | Every vertex can reach every other vertex | A road network with no cut-off town |
| Disconnected | Some vertices cannot reach others | Two islands with no bridge |
| Cyclic | Contains at least one cycle | A ring road |
| Acyclic | Contains no cycle | A family tree |
| DAG (directed acyclic graph) | Directed edges and no cycle | Course prerequisites, build order |
Connected vs disconnected graph
In a connected graph you can walk from any vertex to any other. In a disconnected graph at least one pair has no path between them, and the graph splits into two or more connected components. A traversal from one vertex only visits its own component, so to cover a disconnected graph you loop over all vertices and start a new traversal at each one you have not seen.
Cyclic vs acyclic graph
A cyclic graph has at least one cycle, a path that returns to its starting vertex. An acyclic graph has none. A connected, acyclic, undirected graph is a tree, and a tree with n vertices has exactly n - 1 edges. A DAG is the directed version: you can never follow its edges back to where you began. That makes a DAG fit for tasks with prerequisites, because the tasks can be put in a topological order where each task comes after the ones it needs.
Adjacency list vs adjacency matrix
These are the two standard ways to store a graph in memory. An adjacency list keeps, for each vertex, the list of its neighbours. An adjacency matrix is a V by V grid where a 1 in row u, column v means there is an edge from u to v. This code builds both for the same five-vertex graph:
nodes = ["A", "B", "C", "D", "E"]
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]
# adjacency list: each node maps to the list of its neighbours
adj = {n: [] for n in nodes}
for u, v in edges:
adj[u].append(v)
adj[v].append(u) # undirected: store the edge both ways
# adjacency matrix: a grid where 1 means "there is an edge"
pos = {n: i for i, n in enumerate(nodes)}
matrix = [[0] * len(nodes) for _ in nodes]
for u, v in edges:
matrix[pos[u]][pos[v]] = 1
matrix[pos[v]][pos[u]] = 1
print(adj)
for row in matrix:
print(row)
print("B-D edge?", "D" in adj["B"], matrix[pos["B"]][pos["D"]] == 1)Output:
{'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C', 'E'], 'E': ['D']}
[0, 1, 1, 0, 0]
[1, 0, 0, 1, 0]
[1, 0, 0, 1, 0]
[0, 1, 1, 0, 1]
[0, 0, 0, 1, 0]
B-D edge? True True| Adjacency list | Adjacency matrix | |
|---|---|---|
| Memory | O(V + E) | O(V^2) |
| Is there an edge between u and v? | O(degree of u) | O(1) |
| List all neighbours of u | O(degree of u) | O(V) |
| Add an edge | O(1) | O(1) |
| Remove an edge | O(degree of u) | O(1) |
| Visit every vertex and edge (BFS or DFS) | O(V + E) | O(V^2) |
| Best for | Sparse graphs, which is most real data | Small or dense graphs, or constant-time edge checks |
Use an adjacency list unless the graph is small and dense. In interviews the input usually arrives as a list of edges, so the first step is building a dictionary of lists, which is the hash map pattern.
BFS and DFS: the two ways to explore a graph
Breadth-first search (BFS) visits the start vertex, then all its neighbours, then their neighbours, and so on, using a queue (see applications of queue). In an unweighted graph it finds the fewest-edges path. Depth-first search (DFS) follows one branch as far as it goes, then backs up, using recursion or a stack (see recursion).
| BFS | DFS | |
|---|---|---|
| Uses | A queue | Recursion or a stack |
| Order | Nearest vertices first, level by level | One branch to its end, then back up |
| Good for | Shortest path by edge count, nearest match, level problems | Connectivity, cycles, components, topological order, backtracking |
| Time | O(V + E) | O(V + E) |
| Extra memory | O(V), the queue can hold a whole level | O(V), the stack can hold the longest path |
Python version. The graph has a second component, G and H, that no search from A can reach:
from collections import deque
graph = {
"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
"D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E"],
"G": ["H"], "H": ["G"], # G and H are a separate component
}
def bfs(start):
"""Fewest edges from start to every reachable node."""
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
def dfs(node, seen=None, order=None):
"""Visit order of a recursive depth-first search."""
seen = set() if seen is None else seen
order = [] if order is None else order
seen.add(node)
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
dfs(nxt, seen, order)
return order
print(bfs("A"))
print(dfs("A"))Output:
{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
['A', 'B', 'D', 'C', 'E', 'F']The first line is the BFS distance, in edges, from A. G and H are missing because they are in another component. The second line is the DFS visit order. JavaScript version of the same two searches:
const graph = {
A: ["B", "C"], B: ["A", "D"], C: ["A", "D", "E"],
D: ["B", "C", "F"], E: ["C", "F"], F: ["D", "E"],
G: ["H"], H: ["G"],
};
function bfs(start) {
const dist = new Map([[start, 0]]);
const queue = [start];
for (let head = 0; head < queue.length; head++) { // index, not shift(), so it stays fast
const node = queue[head];
for (const next of graph[node]) {
if (!dist.has(next)) {
dist.set(next, dist.get(node) + 1);
queue.push(next);
}
}
}
return Object.fromEntries(dist);
}
function dfs(node, seen = new Set()) {
seen.add(node); // a Set keeps insertion order
for (const next of graph[node]) {
if (!seen.has(next)) dfs(next, seen);
}
return [...seen];
}
console.log(bfs("A"));
console.log(dfs("A").join(" "));Output:
{ A: 0, B: 1, C: 1, D: 2, E: 2, F: 3 }
A B D C E FCount connected components and detect a cycle
These two checks are asked so often that they are worth knowing cold. To count components, start a search from every vertex you have not seen and add one each time. To detect a cycle in an undirected graph, run DFS and report a cycle if you reach an already-seen vertex that is not the one you just came from.
graph = {
"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
"D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E"],
"G": ["H"], "H": ["G"],
}
tree = {"A": ["B", "C"], "B": ["A"], "C": ["A"]} # 3 nodes, 2 edges, no cycle
def count_components(g):
seen, count = set(), 0
for start in g:
if start in seen:
continue
count += 1 # a node we had not reached: new component
stack = [start]
seen.add(start)
while stack:
node = stack.pop()
for nxt in g[node]:
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)
return count
def has_cycle(g):
"""Cycle check for a simple undirected graph (no repeated edges)."""
seen = set()
def visit(node, parent):
seen.add(node)
for nxt in g[node]:
if nxt == parent:
continue # do not treat the edge we came by as a cycle
if nxt in seen or visit(nxt, node):
return True
return False
return any(visit(n, None) for n in g if n not in seen)
print(count_components(graph), has_cycle(graph))
print(count_components(tree), has_cycle(tree))Output:
2 True
1 FalseThe first graph has two components and a cycle (A, B, D, C). The three-vertex tree has one component and no cycle. For a directed graph the "came from" trick does not work, because an edge back to a seen vertex is not always a cycle. Use Kahn's algorithm instead: repeatedly remove vertices that have no incoming edge. If some vertices can never be removed, the graph has a cycle.
// Directed graph with nodes 0..n-1. Kahn's algorithm: repeatedly remove nodes
// with no incoming edge. If some nodes are never removed, the graph has a cycle.
function hasCycle(n, edges) {
const adj = Array.from({ length: n }, () => []);
const indegree = Array(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
indegree[v]++;
}
const queue = [];
indegree.forEach((d, i) => { if (d === 0) queue.push(i); });
let removed = 0;
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
removed++;
for (const v of adj[u]) {
if (--indegree[v] === 0) queue.push(v);
}
}
return removed < n;
}
console.log(hasCycle(4, [[0, 1], [1, 2], [2, 3]])); // a chain: no cycle
console.log(hasCycle(4, [[0, 1], [1, 2], [2, 3], [3, 1]])); // 1 -> 2 -> 3 -> 1Output:
false
trueThe same removal order is a topological order, which the applications of graph page uses for build and dependency ordering.
When to use a graph, and the problem types to expect
Reach for a graph when a problem is about things and the connections between them, or when you can describe it as moves between states. These signals appear again and again in interviews:
| Signal in the problem | How to model it | Usual technique |
|---|---|---|
| Grid of cells: islands, mazes, spreading | Each cell is a vertex, its four neighbours are edges | BFS or DFS |
| Fewest steps, moves or mutations | Each state is a vertex, each move an edge | BFS |
| Cheapest or shortest with different costs | Weighted edges | Dijkstra's algorithm |
| Tasks with prerequisites, ordering, deadlock | Directed edges from need to dependent | Topological sort, cycle check |
| Friends, groups, merging sets | Undirected edges | DFS or Union-Find |
| Split into two teams, two colours | Bipartite check | BFS or DFS colouring |
| Can A reach B? | Any graph | BFS or DFS |
Interview problem families, by name only, so you can read the statements yourself: Number of Islands and Rotting Oranges (grid BFS or DFS), Clone Graph (traversal with a map), Course Schedule and Course Schedule II (cycle detection and topological order), Word Ladder (BFS over states), Network Delay Time (weighted shortest path), Is Graph Bipartite? (colouring) and Redundant Connection (cycle in an undirected graph).
Common mistakes and practice problems
Common mistakes
- No visited set. Any graph with a cycle sends the search round in circles forever.
- Assuming one search covers everything. It covers one component. Loop over all vertices for a disconnected graph.
- Using
list.pop(0)as the BFS queue. It shifts every element, which the Python documentation describes as an O(n) cost. Usecollections.deque. - Marking a vertex visited only when it is dequeued. The same vertex can be queued many times. Mark it when you add it to the queue.
- Storing an undirected edge in one direction only. Add it to both vertices' lists.
- Deep recursion. Python stops a recursive function at about 1,000 nested calls by default, so a long path can crash a recursive DFS. Use an explicit stack for big inputs.
Practice problems, in order
- Find if Path Exists in Graph (traversal basics)
- Number of Provinces (count components)
- Number of Islands (grid as a graph)
- Clone Graph
- Course Schedule (directed cycle)
- Rotting Oranges (multi-source BFS)
- Pacific Atlantic Water Flow
- Word Ladder
Masai's longer guide: Graph Data Structure: Types, Representation, BFS, DFS. Next, see where graphs are used in applications of graph in data structure, then practise on the coding practice websites list or follow the DSA learning path.
Frequently asked questions
What is a graph in data structure?
A data structure made of vertices (nodes) and edges (links between them). It models relationships such as roads between cities or friendships between people, and is usually stored as an adjacency list or an adjacency matrix.
What is a disconnected graph?
A graph in which at least one pair of vertices has no path between them, so it splits into two or more connected components. A search from one vertex reaches only its own component, so start a new search from every unvisited vertex.
What is the difference between a cyclic and an acyclic graph?
A cyclic graph contains at least one cycle, a path that returns to its start. An acyclic graph has none. A directed acyclic graph (DAG) can be ordered so every edge points forward, which is why it is used for task dependencies.
Should I use an adjacency list or an adjacency matrix?
Use an adjacency list for most problems: it takes O(V + E) memory and lists neighbours quickly. Use a matrix only when the graph is small or dense, or when you need O(1) edge checks.
What is the difference between BFS and DFS?
BFS explores level by level with a queue and finds the fewest-edges path in an unweighted graph. DFS follows one branch to the end before backing up, using recursion or a stack, and suits connectivity, cycle detection and topological order. Both run in O(V + E).
How do you detect a cycle in a graph?
In an undirected graph, run DFS and report a cycle if you reach a seen vertex that is not the one you came from. In a directed graph, use Kahn's algorithm: if you cannot remove every vertex by repeatedly taking those with no incoming edge, a cycle exists.
Sources checked
- Adjacency list O(V + E) and adjacency matrix O(V^2) storage costs
- BFS time O(V + E), shortest path in unweighted graphs
- DFS time O(V + E)
- deque O(1) ends; list pop(0) O(n) memory movement
- Existing Masai post (HTTP 200 on 11 Nov 2026)
Learn this with mentors
Programmes for builders and engineers with admissions open: live classes, mentors and project work.


