Problem

Given an undirected, unweighted graph G(V, E) with N vertices and M edges, find the minimum number of edges (i.e., the shortest path in terms of edge count) between two given vertices u and v.

Examples

Example 1

1
2
3
4
5
6
7

Input:
n = 5
edges = [[1, 2], [2, 5], [1, 3]]
source = 1
destination = 5
Output: 2
Explanation: Shortest path (in edges) is 1 → 2 → 5 (2 edges).

Example 2

1
2
3
4
5
6
7
8

Input:
n = 5
edges = [[0, 1], [1, 2], [2, 3], [0, 4], [4, 3]]
source = 0
destination = 3

Output: 2
Explanation: Shortest path (in edges) is 0 → 4 → 3 (2 edges).

Solution

Method 1 – Breadth-First Search (BFS)

Intuition

Breadth-first search (BFS) explores the graph in layers: first all vertices at distance 0 (the source), then all vertices at distance 1, then distance 2, and so on. Because each edge contributes exactly 1 to path length in an unweighted graph, the first time BFS reaches a vertex it has found a shortest path (in number of edges) to that vertex.

One convenient way to see this is by induction on the BFS level. After processing k layers BFS has discovered all vertices at distance <= k and assigned them the correct distance. When BFS expands all vertices at level k it discovers previously-unseen neighbors and labels them distance k+1; by construction these cannot have a shorter path than k+1 because any path to them must come through some vertex at level <= k.

Equivalently, BFS implicitly builds a BFS tree rooted at the source; the tree path to any vertex is a shortest (edge-count) path in the original graph.

This is how above BFS tree may look:

graph TB
    A("s")
    A --- B1("1")
    A --- B2("1")
    A --- B3("1")
    A --- B4("1")
    A --- B5("1")
    A --- B6("1")
    A --- B7("1")
    A --- B8("1")

    B1 --- C1("2")
    B2 --- C2("2")
    B3 --- C3("2")
    B4 --- C4("2")
    B5 --- C5("2")
    B6 --- C6("2")
    B7 --- C7("2")
    B8 --- C8("2")

Approach

  1. Initialize a queue and a visited array for all vertices.
  2. Start BFS from the source vertex u, marking it visited and setting its distance to 0.
  3. For each vertex dequeued, enqueue all unvisited neighbors, updating their distance as distance of current + 1.
  4. Stop when the target vertex v is reached; its distance is the answer.
  5. If v is unreachable, return -1.

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

dist(v) = { 0 if v = source else infinity }

foreach vertex v in all vertices {
    if (v == source)
        dist(v) = 0;
    else
        dist(v) = infinity;
}

Q := queue containing source
while Q is not empty:
    u := Q.dequeue()
    for each neighbor v of u:
        if dist(v) is infinity:
            dist(v) := dist(u) + 1
            predecessor(v) := u
            Q.enqueue(v)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Assumes vertices are 0-based. If your input is 1-based, convert to 0-based before calling.
class Solution {
public:
    // n: number of vertices
    // edges: list of undirected edges where each edge is a vector {u, v}
    // source, dest: start and target vertices (0-based)
    int minEdgeBFS(int n, const vector<vector<int>>& edges, int source, int dest) {
        vector<vector<int>> adj(n);
        for (const auto &e : edges) {
            int u = e[0], v = e[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        vector<int> dist(n, -1);
        queue<int> q;
        dist[source] = 0;
        q.push(source);
        while (!q.empty()) {
            int x = q.front(); q.pop();
            if (x == dest) return dist[x];
            for (int nei : adj[x]) {
                if (dist[nei] == -1) {
                    dist[nei] = dist[x] + 1;
                    q.push(nei);
                }
            }
        }
        return dist[dest]; // -1 if unreachable
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Solution {
    /**
     * n: number of vertices
     * edges: array of edges where each edge is an int[2] {u, v} (0-based)
     * source, dest: 0-based vertex indices
     */
    public int minEdgeBFS(int n, int[][] edges, int source, int dest) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; ++i) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        dist[source] = 0;
        q.add(source);
        while (!q.isEmpty()) {
            int x = q.poll();
            if (x == dest) return dist[x];
            for (int nei : adj.get(x)) {
                if (dist[nei] == -1) {
                    dist[nei] = dist[x] + 1;
                    q.add(nei);
                }
            }
        }
        return dist[dest];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from collections import deque

class Solution:
    def min_edge_bfs(self, n: int, edges: list[list[int]], source: int, dest: int) -> int:
        """n: number of vertices, edges: list of [u, v] pairs (0-based)."""
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        dist = [-1] * n
        dq = deque([source])
        dist[source] = 0
        while dq:
            x = dq.popleft()
            if x == dest:
                return dist[x]
            for nei in adj[x]:
                if dist[nei] == -1:
                    dist[nei] = dist[x] + 1
                    dq.append(nei)
        return dist[dest]

Complexity

  • ⏰ Time complexity: O(N + M), where N is the number of vertices and M is the number of edges, since each vertex and edge is processed at most once.
  • 🧺 Space complexity: O(N), for the visited and distance arrays and the queue.

Application

Finding the shortest path (by edge count) is a fundamental primitive used in many domains: routing and networking, map/navigation, social networks, puzzle solving, and game AI. Running BFS from a source gives you not only the distance to a single target but the shortest distances and predecessors for all reachable vertices in the same O(N + M) time. That extra information is useful for reconstructing paths, computing reachability or eccentricity measures, performing multi-source searches, and as a subroutine in larger algorithms.

When edges have unequal weights, use Dijkstra or Bellman–Ford instead; the BFS approach is the right tool specifically for unweighted or equal-weight graphs.

When not to use BFS

Use BFS only when all edges have equal weight (or when you care about edge-count distance). If edges have non-equal non-negative weights, use Dijkstra’s algorithm (O((N+M) log N) with a heap). If negative edge weights are allowed, use Bellman–Ford (or detect/handle negative cycles).