Neel Mishra
← All Posts
DSA · Bit Manipulation· Part 27 of 32

Bitwise Graph and Search Problems

May 2026 · 26 min read

When a graph state includes "which items have been collected" or "which nodes have been visited", a bitmask often becomes part of the BFS or DP state. This turns graph search into search over an expanded state graph.

BFS Over Masks

Shortest path visiting all nodes is the canonical example. The state is (node, visitedMask).

queue<pair<int,int>> q;
dist[node][mask] = 0;

while (!q.empty()) {
    auto [u, mask] = q.front();
    q.pop();
    for (int v : graph[u]) {
        int nmask = mask | (1 << v);
        if (dist[v][nmask] == INF) {
            dist[v][nmask] = dist[u][mask] + 1;
            q.push({v, nmask});
        }
    }
}

Keys and Locks

For grid problems with keys, each key is a bit. A lock can be crossed only if its bit is present.

if ('a' <= cell && cell <= 'f') mask |= 1 << (cell - 'a');
if ('A' <= cell && cell <= 'F') {
    if ((mask & (1 << (cell - 'A'))) == 0) continue;
}

Steiner Tree DP

When only a small set of terminals must be connected, use masks over terminals and graph shortest paths.

dp[mask][v] = minimum cost of a connected structure
              ending at v and covering terminal subset mask

Transitions combine submasks at the same vertex, then relax edges with Dijkstra or SPFA depending on weights.

State Dominance

One state can dominate another if it reaches the same place with a superset of resources at no greater cost. Avoid pruning unless the dominance relation is mathematically safe.

Recognition Guide

Practice Problems