liveBook · Manning

Bron–Kerbosch algorithm

As explained in Algorithms Every Programmer Should Know

The Bron–Kerbosch algorithm is a recursive backtracking algorithm for enumerating the maximal cliques of an undirected graph.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through recursive set updates and reporting conditions, then introduces pivoting and its branching benefit.
Examples
Traces cliques {1, 2, 4} and {2, 3, 5}, rejects a duplicate subset, and supplies Python implementations.
What it assumes
Introduces cliques and maximality from vertices and edges before explaining the recursive search.
What you can do after
Build it from scratch to enumerate maximal cliques using recursive set intersections, with optional pivoting.
How it connects
Connects clique enumeration to recursive backtracking, graph clustering, and compatibility graphs for stereo correspondence.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.