A clique is a subset of vertices of a graph such that every two distinct vertices in the clique are adjacent. Finding a clique from a graph is an important problem in graph theory and many algorithms have been proposed to solve this problem. The most popular algorithm for finding a clique is the technique of the most dense subgraph. This technique is based on the fact that a clique is the most dense subgraph of the graph. In this article, we will discuss a Java program to find a clique by using the technique of the most dense subgraph.
Examples
Example 1:
Let’s take a graph G = (V, E) with the following adjacency matrix:
V = {v1, v2, v3, v4}
E = {(v1, v2), (v2, v3), (v3, v4), (v1, v4)}
Adjacency Matrix:
[[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]]The most dense subgraph of the graph G is the clique {v1, v2, v3, v4}.
Example 2:
Let’s take another graph G = (V, E) with the following adjacency matrix:
V = {v1, v2, v3, v4, v5}
E = {(v1, v2), (v2, v3), (v3, v4), (v4, v5), (v1, v5)}
Adjacency Matrix:
[[0, 1, 0, 0, 1],
[1, 0, 1, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 1, 0, 1],
[1, 0, 0, 1, 0]]The most dense subgraph of the graph G is the clique {v1, v2, v3, v4}.
Approach
The approach used in the program is based on the technique of the most dense subgraph. The algorithm works as follows:
- Initialize an array of size equal to the number of vertices in the graph.
- For each vertex, count the number of edges connected to it.
- Find the vertex with the maximum number of edges and mark it as the first vertex of the clique.
- For each of the remaining vertices in the graph, count the number of edges connected to both the first vertex and the current vertex.
- If the number of edges is equal to the number of vertices in the clique, then add the current vertex to the clique.
- Repeat Steps 4 and 5 until all the vertices have been checked.
Below is the implementation of the above approach.
Implementation
Java
// Java Program for the above approachimport java.util.ArrayList;import java.util.List; public class CliqueFinder { static int[][] adjMatrix; static int cliqueSize; static List<Integer> clique; // Function to initialize the adjacency matrix static void init(int[][] adjMatrix) { clique = new ArrayList<Integer>(); for (int i = 0; i < adjMatrix.length; i++) { int count = 0; for (int j = 0; j < adjMatrix.length; j++) { if (adjMatrix[i][j] == 1) count++; } if (count > cliqueSize) { cliqueSize = count; clique.clear(); clique.add(i); } } } // Function to find the clique static void findClique(int[][] adjMatrix) { for (int i = 0; i < adjMatrix.length; i++) { if (!clique.contains(i)) { int count = 0; for (int j = 0; j < clique.size(); j++) { if (adjMatrix[i][clique.get(j)] == 1) count++; } if (count == cliqueSize) { clique.add(i); } } } } // Driver code public static void main(String[] args) { int[][] adjMatrix = { { 0, 1, 0, 1 }, { 1, 0, 1, 0 }, { 0, 1, 0, 1 }, { 1, 0, 1, 0 } }; init(adjMatrix); findClique(adjMatrix); // Print the clique System.out.println("The clique is: "); for (int i = 0; i < clique.size(); i++) { System.out.print(clique.get(i) + " "); } }} |
The clique is: 0
