Dado un gráfico que consta de N Nodes y una array edge [][] que denota un borde de edge [i][0] con edge [i][1] . Dado un Node K , la tarea es encontrar el Node que tiene el máximo número de Nodes comunes con K .
Ejemplos:
Entrada: K = 1, N = 4, aristas = {{1, 2}, {1, 3}, {2, 3}, {3, 4}, {2, 4}}
Salida: 4
Explicación: El gráfico formado por aristas dadas se muestra a continuación.
Dado K = 1, los Nodes adyacentes a todos los Nodes están por debajo
de 1: 2, 3
2: 1, 3, 4
3: 1, 2, 4
4: 2, 3
Claramente, el Node 4 tiene un máximo de Nodes comunes con el Node 1. Por lo tanto , 4 es la respuesta.
Entrada: K = 2, N = 3, bordes = {{1, 2}, {1, 3}, {2, 3}}
Salida: 3
Enfoque: este problema se puede resolver utilizando la búsqueda en amplitud . Siga los pasos a continuación para resolver el problema dado.
- La idea es usar BFS con la fuente como un Node dado (nivel 0).
- Almacene todos los vecinos de un Node dado en una lista, digamos al1 (nivel 1)
- Ahora mantenga otra lista al2 y almacene cada nivel en BFS y cuente los elementos comunes de al1 con al2 .
- Mantenga la variable max para mantener el conteo de amigos comunes máximos y otra variable mostAppnode para almacenar la respuesta del problema dado.
- Devuelve mostAppnode .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// No. of nodes
int V;
// Adjacency Lists
vector<vector<int> > adj;
// Neighbours of given node stored in al1
vector<int> al1;
void create_Graph(int v)
{
V = v;
adj = {};
for (int i = 0; i < v; ++i)
adj.push_back({});
}
// Function to add an edge into the graph
void addEdge(int v, int w)
{
adj[(v - 1)].push_back(w - 1);
adj[(w - 1)].push_back(v - 1);
}
// find element in queue
bool contains(queue<int> q, int n)
{
while (q.size()) {
if (q.front() == n)
return 1;
q.pop();
}
return false;
}
int BFS(int s)
{
// Mark all the vertices as not visited
// (By default set as false)
bool visited[V] = { 0 };
// Create a queue for BFS
queue<int> queue;
// Mark the current node
// as visited and enqueue it
visited[s] = true;
queue.push(s);
int c = 0;
// Max common nodes with given node
int max = 0;
int mostAppnode = 0;
// To store common nodes
int count = 0;
while (queue.size() != 0) {
// Dequeue a vertex from queue
s = queue.front();
queue.pop();
// Get all adjacent nodes
// of the dequeued node
// If a adjacent has
// not been visited, then
// mark it visited and enqueue it
c++;
vector<int> al2;
int i = 0;
while (i < adj[s].size()) {
int n = adj[s][i];
if (c == 1)
al1.push_back(n);
else
al2.push_back(n);
// If node is not
// visited and also not
// present in queue.
if (!visited[n] && !contains(queue, n)) {
visited[n] = true;
queue.push(n);
}
i++;
}
if (al2.size() != 0) {
for (int frnd : al2) {
if (find(al1.begin(), al1.end(), frnd)
!= al1.end())
count++;
}
if (count > max) {
max = count;
mostAppnode = s;
}
}
}
if (max != 0)
return mostAppnode + 1;
else
return -1;
}
// Driver Code
int main()
{
int N = 4;
create_Graph(4);
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 3);
addEdge(3, 4);
addEdge(2, 4);
int K = 1;
cout << (BFS(K - 1)) << endl;
}
// This code is contributed by rj13to.
Java
// Java implementation of above approach
import java.io.*;
import java.util.*;
class Graph {
// No. of nodes
private int V;
// Adjacency Lists
private ArrayList<ArrayList<Integer> > adj;
// Neighbours of given node stored in al1
ArrayList<Integer> al1 = new ArrayList<>();
// Constructor
Graph(int v)
{
V = v;
adj = new ArrayList<>();
for (int i = 0; i < v; ++i)
adj.add(new ArrayList<Integer>());
}
// Function to add an edge into the graph
void addEdge(int v, int w)
{
adj.get(v - 1).add(w - 1);
adj.get(w - 1).add(v - 1);
}
private int BFS(int s)
{
// Mark all the vertices as not visited
// (By default set as false)
boolean visited[] = new boolean[V];
// Create a queue for BFS
LinkedList<Integer> queue
= new LinkedList<Integer>();
// Mark the current node
// as visited and enqueue it
visited[s] = true;
queue.add(s);
int c = 0;
// Max common nodes with given node
int max = 0;
int mostAppnode = 0;
// To store common nodes
int count = 0;
while (queue.size() != 0) {
// Dequeue a vertex from queue
s = queue.poll();
// Get all adjacent nodes
// of the dequeued node
// If a adjacent has
// not been visited, then
// mark it visited and enqueue it
c++;
ArrayList<Integer> al2
= new ArrayList<>();
Iterator<Integer> i
= adj.get(s).listIterator();
while (i.hasNext()) {
int n = i.next();
if (c == 1)
al1.add(n);
else
al2.add(n);
// If node is not
// visited and also not
// present in queue.
if (!visited[n]
&& !queue.contains(n)) {
visited[n] = true;
queue.add(n);
}
}
if (al2.size() != 0) {
for (int frnd : al2) {
if (al1.contains(frnd))
count++;
}
if (count > max) {
max = count;
mostAppnode = s;
}
}
}
if (max != 0)
return mostAppnode + 1;
else
return -1;
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
Graph g = new Graph(4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(2, 4);
int K = 1;
System.out.println(g.BFS(K - 1));
}
}
Python3
# python implementation of above approach # Neighbours of given node stored in al1 al1 = [] # Function to add an edge into the graph def addEdge(v, w, adj): adj[v - 1].append(w - 1) adj[w - 1].append(v - 1) def BFS(s, adj, V): # Mark all the vertices as not visited # (By default set as false) visited = [False] * V # Create a queue for BFS queue = [] # Mark the current node # as visited and enqueue it visited[s] = True queue.append(s) c = 0 # Max common nodes with given node max = 0 mostAppnode = 0 # To store common nodes count = 0 while (len(queue) != 0): # Dequeue a vertex from queue s = queue[0] queue.pop(0) # Get all adjacent nodes # of the dequeued node # If a adjacent has # not been visited, then # mark it visited and enqueue it c += 1 al2 = [] for i in adj[s]: n = i if (c == 1): al1.append(n) else: al2.append(n) # If node is not # visited and also not # present in queue. is_contained = False if(n in queue): is_contained = True if ((visited[n] == False) and (is_contained == False)): visited[n] = True queue.append(n) if (len(al2) != 0): for frnd in al2: if (frnd in al1): count += 1 if (count > max): max = count mostAppnode = s if (max != 0): return mostAppnode + 1 else: return -1 # Driver Code N = 4 # list to store connections adj = [[]]*N addEdge(1, 2, adj) addEdge(1, 3, adj) addEdge(2, 3, adj) addEdge(3, 4, adj) addEdge(2, 4, adj) K = 1 print(BFS(K - 1, adj, N)) # This code is contributed by rj13to.
Producción
4
Complejidad de tiempo: O (V*V), BFS tomará tiempo O(V+E) pero encontrar elementos comunes entre al1 y al2 tomará tiempo O(V*V).
Espacio Auxiliar: O(V)
Publicación traducida automáticamente
Artículo escrito por iramkhalid24 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA