Hacer un BFS servirá a su propósito.
A continuación se muestra cómo hacer el cálculo en un solo nodo de un clúster (si todos los datos están presentes en un nodo).
Suponga que la persona A y la persona B están separadas por la distancia d. Luego, simplemente haciendo BFS desde estos dos nodos en paralelo, obtendremos los amigos comunes después de hacer el BFS hasta el nivel d / 2.
Suponiendo que tenemos una ramificación constante de cada nodo en promedio es ‘x’. luego, en el nivel d / 2 hemos investigado [matemáticas] x ^ {d / 2} [/ matemáticas] nodos de cada persona.
Entonces, en total [math] 2 * (x ^ {d / 2}) [/ math], los nodos han sido atravesados.
Ahora, una vez que tengamos la lista de amigos de estos dos nodos, podemos ejecutar las intersecciones entre ellos, para esto primero encontraremos a todos los amigos y amigos de A (es decir, obtenidos al hacer BFS y el algoritmo paralelo realizará comprobaciones en nodos comunes, es decir intersección entre estos dos conjuntos de amigos).
La intersección de conjunto tomará alrededor de O (m + n), para conjuntos de longitud m & n.
- ¿Abordas los problemas de codificación de entrevistas de manera diferente a los problemas reales?
- Cómo recordar algoritmos como KMP y la búsqueda de cadenas de Boyer-Moore en preparación para grandes empresas tecnológicas como Amazon, Flipkart, etc.
- No he recibido respuesta 2 meses después de una entrevista en una empresa de alta tecnología. ¿Tengo alguna posibilidad de conseguir el trabajo?
- ¿Cómo puede un entrevistador seleccionar un programador haciendo algunas preguntas técnicas? El candidato puede ser mejor codificando que respondiendo las preguntas.
- ¿Qué debo saber sobre C ++ antes de poder escribir 'competente en C ++' en mi currículum?
Sin embargo, el ingenuo BFS tomará tomar O ([matemáticas] x ^ d [/ matemáticas]).
Si suponemos que [math] x ^ {d} [/ math] = r, entonces el BFS retorcido tomará, [math] \ sqrt [2] {r} [/ math], que es mucho más rápido que hacer un BFS ingenuo.
El cálculo distribuido realmente requerirá aquí, porque todos los datos de nodo (datos de amigos de amigos, es decir, amigos de campo a través) residirán en un sistema diferente.
Para obtener un conocimiento más profundo al respecto, puede consultar el siguiente documento:
Página en supercomputing.org