Suppose a social network needs to find groups in which everyone is directly connected to everyone else. Such a group is a clique. A maximal clique cannot be enlarged without losing that property. “Maximal” does not mean “the single largest”: a graph can have several maximal cliques of different sizes. Bron–Kerbosch finds all of them without generating every possible group of vertices. section 11.1
The recursive search keeps three sets:
- R contains the mutually connected vertices already chosen. section 11.1
- P contains vertices that could still join R. When choosing a vertex, intersect P with its neighbors so incompatible candidates drop out. section 11.1
- X contains previously explored vertices that could also join R. It prevents an already covered clique from being reported again. section 11.1
Start with R and X empty and every graph vertex in P. For each candidate v, recurse with v added to R and with both P and X restricted to neighbors of v. After that branch returns, move v from P to X. Report R only when both P and X are empty: no eligible vertex can extend it, and no previously explored vertex shows that it belongs to a clique already covered. section 11.1
Two branches, two different endings
One branch grows R to {1, 2, 4}; with P and X both empty, that group is reported. Another reaches {2, 4} with P empty but vertex 1 still in X, so it reports nothing: {2, 4} sits inside the earlier clique. A later branch reaches {2, 3, 5} with both sets empty and reports a second maximal clique. section 11.1
Figure 11.2 The example graph and three sets, R, P, and X. R, the clique being built so far (all mutually connected), P, the candidates still connected to everything in R and therefore still eligible to join it, and X, the vertices already fully explored, kept around only so the algorithm never reports the same maximal clique twice. The initial call starts with R and X empty and P holding every vertex in the graph.
The graph and initial R, P, and X sets make the recursive state easier to follow. section 11.1
Listing 11.1 Pseudocode of Bron-Kerbosch Algorithm
Input:
R : Set of vertices currently forming the clique
P : Set of candidate vertices that can extend R
X : Set of already-evaluated vertices (to avoid duplicate cliques)
Output:
All maximal cliques containing R, candidates from P, and no vertices from X
if P is empty and X is empty then
output R as a maximal clique
return
end if
for each vertex v in a copy of P do
neighbors_v = GetNeighbors(v)
new_R = R ∪ {v}
new_P = P ∩ neighbors_v
new_X = X ∩ neighbors_v
BronKerbosch(new_R, new_P, new_X)
P = P \ {v}
X = X ∪ {v}
end for
Pseudocode shows the neighbor intersections, recursive call, and move from P to X together. section 11.1
Pivoting cuts down branches: choose a pivot from P or X and try only candidates in P that are not its neighbors. The search still faces graphs with very many maximal cliques, so output size can make a run expensive. Beyond social groups, compatibility graphs use cliques to find sets of mutually consistent candidate matches between two camera views. section 11.4 section 11.2
