Graph

Graphs are one of the most important concepts to master for coding interviews because they model relationships. Many LeetCode problems are secretly graph problems even when the input looks like a grid, a list of words, or a set of dependencies. Once you learn how to represent graphs and traverse them safely, a large class of hard-looking problems becomes much more predictable.

In simple terms, a graph is a set of nodes connected by edges. Unlike trees, graphs are not necessarily hierarchical, and they may contain cycles, multiple paths, and disconnected groups. That flexibility is exactly why graphs show up so often in interview settings.

What is a graph?

A graph is a non-linear data structure that represents relationships between objects. Formally, a graph is defined as an ordered pair G = (V, E), where:

• V is a set of vertices (also called nodes).
• E is a set of edges that connect pairs of vertices.

Each vertex represents an entity (for example, a person, city, or web page). Each edge represents a relationship between two entities (for example, friendship, a road, or a hyperlink).

Depending on the problem, edges may also include additional information such as a weight (cost, distance, or time), and they may be directed or undirected.

Graph vs. Tree

The table below summarizes the most important differences between graphs and trees.

Real-world intuition

Graphs are easier to understand when you connect them to real-world systems that consist of entities and relationships:

• Maps and navigation: Cities (or intersections) are nodes, and roads are edges.
• Social networks: Users are nodes, and friendships relationships form edges.
• The web: Web pages are nodes, and hyperlinks between pages are directed edges.
• Airline networks: Airports are nodes, and flights are edges.

In short, a graph is a natural model for any problem that involves a set of items and the connections between them.

Types of graphs

In coding interviews, most graphs can be classified using a few core properties:

Undirected graphs

In an undirected graph, edges have no direction, so the connection works both ways (A — B). This model is common in scenarios such as mutual friendships or two-way roads.

Directed graphs

In a directed graph, each edge has a direction (A → B), meaning the relationship goes one way. This is used for dependencies, prerequisites, or one-way routes.

Weighted graphs

In a weighted graph, each edge carries a numerical value called a weight, such as distance, cost, or travel time. Weighted graphs can be either directed or undirected, depending on whether the relationship is one-way or two-way. They are used when you need the minimum-cost route rather than the fewest steps.

Unweighted graphs

In an unweighted graph, all edges are treated as having the same cost (typically cost = 1). Unweighted graphs can also be directed or undirected, depending on whether edges have direction. These graphs are common when the problem asks for the minimum number of moves or steps.

Cyclic graphs

A cyclic graph contains at least one cycle, meaning there exists a path that starts and ends at the same node.

Acyclic graphs

An acyclic graph contains no cycles. A particularly important case is a Directed Acyclic Graph (DAG), which is a directed graph with no cycles and is common in dependency problems.

Graph terminology for coding interviews

Coding interview questions rely on standard graph terminology. The following definitions are used consistently across most problems:

• Vertex (node): A single entity in the graph.
• Edge: A connection between two vertices.
• Neighbor (adjacent vertex): A vertex that is directly connected to another vertex by an edge.
• Degree: The number of edges incident to a vertex (i.e., the number of connections it has).
  • In a directed graph, degree is split into:
    • Indegree: The number of incoming edges to a vertex.
    • Outdegree: The number of outgoing edges from a vertex.
• Path: A sequence of vertices where each consecutive pair is connected by an edge.
• Cycle: A path that starts and ends at the same vertex, with at least one edge.
• Connected component: In an undirected graph, a maximal group of vertices such that every vertex in the group is reachable from every other vertex in the same group.
• Reachable: A vertex B is reachable from vertex A if there exists at least one path from A to B.

Graph representations in code

Graphs can be represented in multiple ways, and choosing the right one affects both performance and implementation clarity. In interviews, the adjacency list is the most common representation, but adjacency matrices and edge lists appear in specific problem types.

Adjacency list

An adjacency list stores, for each node, a list of the nodes directly connected to it (its neighbors). This representation is memory-efficient for sparse graphs, which is the typical case in interview problems.

Python implementation for adjacency list (unweighted)

# adj[u] = list of neighbors of u
adj = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
}

Python implementation for adjacency list (weighted)

# adj[u] = list of (neighbor, weight)
adj = {
    0: [(1, 5), (2, 2)],
    1: [(3, 1)],
    2: [(1, 2)],
    3: []
}

Adjacency matrix

An adjacency matrix is a V × V table where matrix[u][v] indicates whether an edge exists between u and v. In a weighted graph, the cell often stores the edge weight (or a sentinel like infinity if no edge exists).

Python implementation for adjacency matrix (unweighted)

V = 4
matrix = [[0] * V for _ in range(V)]
matrix[0][1] = 1
matrix[1][0] = 1  # include this for undirected graphs

Python implementation for adjacency matrix (weighted)

INF = 10**15
V = 4
matrix = [[INF] * V for _ in range(V)]
for i in range(V):
    matrix[i][i] = 0

matrix[0][1] = 5
matrix[1][0] = 5  # include this for undirected graphs

Edge list

An edge list stores the graph as a list of edges. Each entry is typically (u, v) for an unweighted graph or (u, v, w) for a weighted graph.

Python implementation for edge list

# unweighted
edges = [(0, 1), (0, 2), (1, 3)]

# weighted
edges = [(0, 1, 5), (0, 2, 2), (1, 3, 1)]

Graph traversal techniques

Most graph problems are solved by traversing the graph: starting from a node and systematically visiting all nodes that are reachable from it. The two fundamental traversal strategies are DFS and BFS.

Depth-first search (DFS)

Depth-first search (DFS) explores as far as possible along one path before backtracking to explore other branches. DFS is a natural fit when you want to fully explore a region or detect cycles.

Python template (iterative DFS)

def dfs(start, adj):
    # visited tracks nodes we have already discovered
    visited = set()

    # stack stores nodes to explore next (LIFO)
    stack = [start]

    # mark the start node as discovered
    visited.add(start)

    while stack:
        # take the most recently added node
        node = stack.pop()

        # ----------------------------------------
        # (optional) do work with node here
        # e.g., print(node) or accumulate results
        # ----------------------------------------

        # explore all neighbors of this node
        for nei in adj[node]:
            # if neighbor has not been discovered yet
            if nei not in visited:
                visited.add(nei)      # mark as discovered immediately
                stack.append(nei)     # schedule neighbor for exploration

    # return all reachable nodes (optional)
    return visited

Time complexity: O(V + E) Space complexity: O(V) in the worst case (visited set + recursion stack or explicit stack)

Python template (recursive DFS)

def dfs(start, adj):
    # visited tracks nodes already explored
    visited = set()

    def helper(node):
        visited.add(node)  # mark node as visited when we enter it

        # (optional) do work with node here

        for nei in adj[node]:
            if nei not in visited:   # avoid revisiting nodes
                helper(nei)          # recursively explore neighbor

    helper(start)  # start DFS from the given node
    return visited

Time complexity: O(V + E) Space complexity: O(V) in the worst case (visited set + recursion stack or explicit stack)

Now, let’s look at the following illustration for the better understanding of DFS.

1 / 11

Breadth-first search (BFS)

Breadth-first search (BFS) explores the graph level by level, visiting all neighbors of the current frontier before moving outward. BFS is the standard tool when the problem asks for the minimum number of steps in an unweighted graph.

Python template (BFS)

from collections import deque

def bfs(start, adj):
    # visited tracks nodes already discovered
    visited = set([start])

    # dist stores the shortest distance (in edges) from start
    dist = {start: 0}

    # queue stores nodes to explore next (FIFO)
    q = deque([start])

    while q:
        node = q.popleft()  # process the oldest discovered node

        # (optional) do work with node here

        for nei in adj[node]:
            if nei not in visited:
                visited.add(nei)             # mark as discovered immediately
                dist[nei] = dist[node] + 1   # first time reached => shortest path
                q.append(nei)                # enqueue neighbor for later processing

    return dist

Time complexity: O(V + E)

Space complexity: O(V) in the worst case (queue + visited)

Now, let’s look at the following illustration for the better understanding of BFS.

1 / 12

Important graph algorithms

Beyond BFS and DFS, the following graph algorithms show up frequently in coding interviews. You do not always need to implement every one from scratch, but you should know what each algorithm solves and when to apply it.