logo CodeStepByStep logo


Language/Type: C++ Graph collections
Related Links:
Author: Marty Stepp (on 2016/06/16)

Write a function named hasClique that accepts two parameters: a reference to a BasicGraph, and an integer K. The goal of your function is to see whether it is possible to form a "clique" of K vertexes in the given graph. In graph theory, a clique is a strongly connected subset of vertexes such that every pair of vertexes in the clique is connected by an edge. Trivially, every vertex itself is a 1-clique, and every pair of vertexes directly connected by an edge is a 2-clique. A 3-clique would be a triangle with each vertex connected to every other; a 4-clique would be 4 vertexes with edges between every pair of them; and so on. The diagram below shows examples of various cliques.

Graph 1 with a 3-clique: {1, 2, 5}
graph 1
Graph 2 with a 4-clique: {d, g, n, r}
graph 2

If your function were passed the above Graph 1 and the K value of 3 or less, should return the boolean result of true to indicate that a suitable clique does exist. If passed a larger value, your function should return false. (The graph might have just one clique of the given size, or many, or none at all.) If your function were passed the graph above at right and a K value of 4 or less, it would similarly return true, but would return false for K values of 5 or above because no such clique exists in that graph.

You may assume that the graph's state is valid, and that it is undirected and unweighted, and that it contains no self-edges (e.g. from V1 to V1). You may define private helper functions if so desired, and you may construct auxiliary collections as needed to solve this problem. You should not modify the contents of the graph such as by adding or removing vertexes or edges from the graph, though you may modify the state variables inside individual vertexes/edges such as visited, cost, and color.

You may assume that the K value passed is 1 or greater.

Hint: Your algorithm for solving this problem does not need to try to be optimal or clever. Consider exhaustively trying possible arrangements of vertexes to see whether a clique of the given size can be found.

Type your solution here:

This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.

Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.