Dado un gráfico no dirigido con N Nodes y E aristas y un valor K , la tarea es imprimir todo el conjunto de Nodes que forman una camarilla de tamaño K. Una camarilla es un subgrafo completo de un grafo. Ejemplos:
Entrada: N = 5, bordes[] = { {1, 2}, {2, 3}, {3, 1}, {4, 3}, {4, 5}, {5, 3} }, K = 3
Salida: 1 2 3, 3 4 5
Explicación: claramente de la imagen, 1->2->3 y 3->4->5 son los dos subgrafos completos.
Entrada: N = 4, aristas[] = { {1, 2}, {2, 3}, {3, 1}, {4, 3} }, k = 3
Salida: 1 2 3
Explicación: Subgrafo 1-> 2->3 forma un subgrafo completo a partir del grafo dado.
Enfoque: La idea es utilizar la recursividad para resolver el problema anterior. Se encuentran todos los vértices cuyo grado es mayor o igual a (K-1) y se comprueba qué subconjunto de K vértices forman una camarilla. Cuando se agrega otro borde a la lista actual, se verifica si al agregar ese borde, la lista todavía forma una camarilla o no.
Se pueden seguir los siguientes pasos para calcular el resultado:
- Forme una función recursiva con tres parámetros Node inicial, longitud del conjunto actual de Nodes y longitud deseada de Nodes.
- El índice inicial parece que no se puede agregar ningún Node al conjunto actual menos que ese índice. Entonces se ejecuta un bucle desde ese índice hasta n.
- Si se encuentra que después de agregar un Node al conjunto actual, el conjunto de Nodes sigue siendo una camarilla. En caso afirmativo, se agrega ese Node y se llama a la función recursiva con el índice de parámetros del nuevo Node agregado +1, la longitud del conjunto actual + 1 y la longitud deseada.
- Si se alcanza la longitud deseada, se imprimen los Nodes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
// Stores the vertices
int store[MAX], n;
// Graph
int graph[MAX][MAX];
// Degree of the vertices
int d[MAX];
// Function to check if the given set of vertices
// in store array is a clique or not
bool is_clique(int b)
{
// Run a loop for all the set of edges
// for the select vertex
for (int i = 1; i < b; i++) {
for (int j = i + 1; j < b; j++)
// If any edge is missing
if (graph[store[i]][store[j]] == 0)
return false;
}
return true;
}
// Function to print the clique
void print(int n)
{
for (int i = 1; i < n; i++)
cout << store[i] << " ";
cout << ", ";
}
// Function to find all the cliques of size s
void findCliques(int i, int l, int s)
{
// Check if any vertices from i+1 can be inserted
for (int j = i + 1; j <= n - (s - l); j++)
// If the degree of the graph is sufficient
if (d[j] >= s - 1) {
// Add the vertex to store
store[l] = j;
// If the graph is not a clique of size k
// then it cannot be a clique
// by adding another edge
if (is_clique(l + 1))
// If the length of the clique is
// still less than the desired size
if (l < s)
// Recursion to add vertices
findCliques(j, l + 1, s);
// Size is met
else
print(l + 1);
}
}
// Driver code
int main()
{
int edges[][2] = { { 1, 2 },
{ 2, 3 },
{ 3, 1 },
{ 4, 3 },
{ 4, 5 },
{ 5, 3 } },
k = 3;
int size = sizeof(edges) / sizeof(edges[0]);
n = 5;
for (int i = 0; i < size; i++) {
graph[edges[i][0]][edges[i][1]] = 1;
graph[edges[i][1]][edges[i][0]] = 1;
d[edges[i][0]]++;
d[edges[i][1]]++;
}
findCliques(0, 1, k);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int MAX = 100;
// Stores the vertices
static int []store = new int[MAX];
static int n;
// Graph
static int [][]graph = new int [MAX][MAX];
// Degree of the vertices
static int []d = new int[MAX];
// Function to check if the given set of vertices
// in store array is a clique or not
static boolean is_clique(int b)
{
// Run a loop for all the set of edges
// for the select vertex
for (int i = 1; i < b; i++)
{
for (int j = i + 1; j < b; j++)
// If any edge is missing
if (graph[store[i]][store[j]] == 0)
return false;
}
return true;
}
// Function to print the clique
static void print(int n)
{
for (int i = 1; i < n; i++)
System.out.print(store[i] + " ");
System.out.print(", ");
}
// Function to find all the cliques of size s
static void findCliques(int i, int l, int s)
{
// Check if any vertices from i+1 can be inserted
for (int j = i + 1; j <= n - (s - l); j++)
// If the degree of the graph is sufficient
if (d[j] >= s - 1)
{
// Add the vertex to store
store[l] = j;
// If the graph is not a clique of size k
// then it cannot be a clique
// by adding another edge
if (is_clique(l + 1))
// If the length of the clique is
// still less than the desired size
if (l < s)
// Recursion to add vertices
findCliques(j, l + 1, s);
// Size is met
else
print(l + 1);
}
}
// Driver code
public static void main(String[] args)
{
int edges[][] = { { 1, 2 },
{ 2, 3 },
{ 3, 1 },
{ 4, 3 },
{ 4, 5 },
{ 5, 3 } },
k = 3;
int size = edges.length;
n = 5;
for (int i = 0; i < size; i++)
{
graph[edges[i][0]][edges[i][1]] = 1;
graph[edges[i][1]][edges[i][0]] = 1;
d[edges[i][0]]++;
d[edges[i][1]]++;
}
findCliques(0, 1, k);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach
import numpy as np
MAX = 100;
# Stores the vertices
store = [0]* MAX;
# Graph
graph = np.zeros((MAX, MAX));
# Degree of the vertices
d = [0] * MAX;
# Function to check if the given set of vertices
# in store array is a clique or not
def is_clique(b) :
# Run a loop for all the set of edges
# for the select vertex
for i in range(1, b) :
for j in range(i + 1, b) :
# If any edge is missing
if (graph[store[i]][store[j]] == 0) :
return False;
return True;
# Function to print the clique
def print_cli(n) :
for i in range(1, n) :
print(store[i], end = " ");
print(",", end=" ");
# Function to find all the cliques of size s
def findCliques(i, l, s) :
# Check if any vertices from i+1 can be inserted
for j in range( i + 1, n -(s - l) + 1) :
# If the degree of the graph is sufficient
if (d[j] >= s - 1) :
# Add the vertex to store
store[l] = j;
# If the graph is not a clique of size k
# then it cannot be a clique
# by adding another edge
if (is_clique(l + 1)) :
# If the length of the clique is
# still less than the desired size
if (l < s) :
# Recursion to add vertices
findCliques(j, l + 1, s);
# Size is met
else :
print_cli(l + 1);
# Driver code
if __name__ == "__main__" :
edges = [ [ 1, 2 ],
[ 2, 3 ],
[ 3, 1 ],
[ 4, 3 ],
[ 4, 5 ],
[ 5, 3 ] ];
k = 3;
size = len(edges);
n = 5;
for i in range(size) :
graph[edges[i][0]][edges[i][1]] = 1;
graph[edges[i][1]][edges[i][0]] = 1;
d[edges[i][0]] += 1;
d[edges[i][1]] += 1;
findCliques(0, 1, k);
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 100;
// Stores the vertices
static int []store = new int[MAX];
static int n;
// Graph
static int [,]graph = new int [MAX, MAX];
// Degree of the vertices
static int []d = new int[MAX];
// Function to check if the given set of vertices
// in store array is a clique or not
static bool is_clique(int b)
{
// Run a loop for all the set of edges
// for the select vertex
for (int i = 1; i < b; i++)
{
for (int j = i + 1; j < b; j++)
// If any edge is missing
if (graph[store[i], store[j]] == 0)
return false;
}
return true;
}
// Function to print the clique
static void print(int n)
{
for (int i = 1; i < n; i++)
Console.Write(store[i] + " ");
Console.Write(", ");
}
// Function to find all the cliques of size s
static void findCliques(int i, int l, int s)
{
// Check if any vertices from i+1 can be inserted
for (int j = i + 1; j <= n - (s - l); j++)
// If the degree of the graph is sufficient
if (d[j] >= s - 1)
{
// Add the vertex to store
store[l] = j;
// If the graph is not a clique of size k
// then it cannot be a clique
// by adding another edge
if (is_clique(l + 1))
// If the length of the clique is
// still less than the desired size
if (l < s)
// Recursion to add vertices
findCliques(j, l + 1, s);
// Size is met
else
print(l + 1);
}
}
// Driver code
public static void Main()
{
int [,]edges = { { 1, 2 },
{ 2, 3 },
{ 3, 1 },
{ 4, 3 },
{ 4, 5 },
{ 5, 3 } };
int k = 3;
int size = edges.GetLength(0);
n = 5;
for (int i = 0; i < size; i++)
{
graph[edges[i, 0], edges[i, 1]] = 1;
graph[edges[i, 1], edges[i, 0]] = 1;
d[edges[i, 0]]++;
d[edges[i, 1]]++;
}
findCliques(0, 1, k);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript implementation of the approach
const MAX = 100;
// Stores the vertices
let store = new Array(MAX).fill(0), n = 0;
// Graph
let graph = new Array(MAX).fill(0).map(() => new Array(MAX).fill(0));
// Degree of the vertices
let d = new Array(MAX).fill(0);
// Function to check if the given set of vertices
// in store array is a clique or not
const is_clique = (b) => {
// Run a loop for all the set of edges
// for the select vertex
for (let i = 1; i < b; i++) {
for (let j = i + 1; j < b; j++)
// If any edge is missing
if (graph[store[i]][store[j]] == 0)
return false;
}
return true;
}
// Function to print the clique
const print = (n) => {
for (let i = 1; i < n; i++)
document.write(`${store[i]} `);
document.write(", ");
}
// Function to find all the cliques of size s
const findCliques = (i, l, s) => {
// Check if any vertices from i+1 can be inserted
for (let j = i + 1; j <= n - (s - l); j++)
// If the degree of the graph is sufficient
if (d[j] >= s - 1) {
// Add the vertex to store
store[l] = j;
// If the graph is not a clique of size k
// then it cannot be a clique
// by adding another edge
if (is_clique(l + 1))
// If the length of the clique is
// still less than the desired size
if (l < s)
// Recursion to add vertices
findCliques(j, l + 1, s);
// Size is met
else
print(l + 1);
}
}
// Driver code
const edges = [
[1, 2],
[2, 3],
[3, 1],
[4, 3],
[4, 5],
[5, 3]
];
let k = 3;
let size = edges.length;
n = 5;
for (let i = 0; i < size; i++) {
graph[edges[i][0]][edges[i][1]] = 1;
graph[edges[i][1]][edges[i][0]] = 1;
d[edges[i][0]]++;
d[edges[i][1]]++;
}
findCliques(0, 1, k);
// This code is contributed by rakeshsahni
</script>
Producción:
1 2 3 , 3 4 5 ,
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA