Algorithms For Dummies

  Discovering Graph Secrets 

     203

1. 

Sort the vertexes by degree (which is the number of vertex connections), from 

the highest to the lowest.

2. 

Place the vertex with the highest degree into the clique (or as an alternative, 

randomly choose from one of the highest-degree vertexes).

3. 

Repeat Steps 1 and 2 until you have no more vertexes to test.

4. 

Verify the next vertex as being part of the clique:

• 

If it’s part of the clique, add it to the clique.

• 

If it isn’t part of the clique, repeat the test on the remaining vertexes.

At the end, after a few algorithm trials, you should have a list of vertexes that 

constitutes the largest clique present in the graph.