liveBook · Manning

Clique

As explained in Algorithms Every Programmer Should Know

A clique is a set of vertices in a graph in which every pair of distinct vertices is connected by an edge.

Imagine a group of users where everyone must be directly connected to everyone else. Represent users as vertices and connections as edges. The group is a clique only if every pair of distinct vertices has an edge between them. One missing connection disqualifies the whole group. section 11.1

Figure 11.1 The left diagram shows every one of the five vertices connects directly to all 4 others, so all possible 10 edges are present, making it a clique. On the other side, we have a missing edge from vertex 2 to 3, which is enough to disqualify the whole group, so it is not a valid clique.

Compare the complete five-vertex group with the group missing just one edge. The missing edge is enough to break the clique. section 11.1

A maximal clique is a clique that cannot be enlarged by adding another vertex. Two connected users form a clique, but may be only a fragment of a larger one. Finding maximal cliques gives each complete group its full boundary rather than returning only smaller overlapping groups. section 11.1

To find every maximal clique, Bron–Kerbosch grows groups through recursive backtracking:

  • Keep R as the clique built so far, P as vertices still eligible to join it, and X as vertices already explored. Start with R and X empty and every vertex in P. section 11.1
  • Choose a vertex from P, add it to R, and intersect P and X with its neighbors. Only vertices compatible with the growing clique continue into that branch. section 11.1
  • Report R only when both P and X are empty. If P is empty but X is not, do not report it: the branch leads to a clique covered by an earlier one. section 11.1

Why the excluded set matters

One branch finds {1, 2, 4} as a maximal clique. A later branch reaches {2, 4} with no candidates left, but vertex 1 remains in X. That group is already contained in the clique found earlier, so it is not reported again. Another branch finds {2, 3, 5}. section 11.1

Generating every vertex subset and testing it is a brute-force alternative, but the number of subsets grows rapidly. Bron–Kerbosch narrows each branch by neighbor intersections; a pivot can reduce branching further. Beyond user groups, a compatibility graph can connect mutually consistent candidate matches between two camera views, making maximal-clique search useful in stereo correspondence. section 11.4 section 11.2

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines cliques and maximality, then traces recursive enumeration, duplicate rejection, and pivoting.
Examples
Uses a five-vertex missing-edge comparison, a traced graph with two maximal cliques, and stereo feature matching.
What it assumes
Assumes basic familiarity with graph vertices and edges while defining cliques and the search sets from scratch.
What you can do after
Apply it via a Python Bron–Kerbosch implementation to enumerate maximal cliques in an undirected graph.
How it connects
Connects cliques to complete subgraphs, maximal cliques, recursive backtracking, graph clustering, and compatibility graphs.

Also explained in

Compare how 2 books explain clique →

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.