Sumérjase en los recorridos de gráficos

Hay más de 2.070 millones de usuarios activos de Facebook en todo el mundo a partir del tercer trimestre de 2017. El aspecto más importante de la red de Facebook es el compromiso social entre los usuarios. Cuantos más amigos tenga un usuario, más atractivas serán las conversaciones a través de comentarios en publicaciones, mensajes, etc. Si ha utilizado Facebook con bastante regularidad, debe conocer la función Recomendación de amigos.

Facebook recomienda un grupo de personas que podemos agregar como amigos. La mayoría de las veces, son personas de las que nunca antes habíamos oído hablar. Pero aún así, Facebook cree que deberíamos agregarlos. La pregunta es: ¿cómo se le ocurre a Facebook un conjunto de recomendaciones para una persona específica ?

Una forma de hacer esto se basa en amigos mutuos. Por ejemplo: - Si un usuario A y C no se conocen, pero tienen un amigo B en común, entonces probablemente A y C también deberían ser amigos. ¿Qué pasa si A y C tienen 2 amigos en común y A y D tienen 3 amigos en común? ¿Cómo será el pedido de sugerencias?

En este caso, parece bastante obvio sugerir D sobre C a A porque tienen más amigos en común y es más probable que se conecten.

Sin embargo, es posible que dos personas no siempre tengan amigos en común, pero pueden tener conexiones comunes de segundo o tercer grado.

Conexiones de enésimo grado

  • A y B son amigos. (0 grados)
  • A y B son amigos de primer grado, lo que significa que tienen un amigo en común.
  • A y B son amigos de segundo grado si tienen un amigo, que es amigo de primer grado de la otra persona. Por ejemplo: - A - C - D - B, entonces A y B son amigos de segundo grado.
  • De manera similar, A y B son amigos de enésimo grado si tienen N conexiones intermedias. ej .: - A - X1 - X2 - X3… .. - XN - B.

Al observar este enfoque para la recomendación, necesitamos poder encontrar el grado de amistad que dos usuarios determinados comparten en Facebook.

Ingresar gráficos recorridos

Ahora que sabemos cómo se pueden hacer las recomendaciones de amigos, replanteemos este problema para que podamos verlo desde una perspectiva algorítmica.

Imaginemos un gráfico no dirigido de todos los usuarios en Facebook , donde los vértices V representan a los usuarios y los bordes E representan amistades. En otras palabras: si los usuarios A y B son amigos en Facebook, hay una ventaja entre los vértices A y B. El desafío consiste en averiguar el grado de conexión entre dos usuarios.

Más formalmente, necesitamos ver la distancia más corta entre dos nodos en un gráfico no ponderado y no dirigido.

Considere dos vértices en este grafo no dirigido A y C. Hay dos caminos diferentes para llegar a C:

1. A → B → C y

2. A → G → F → E → D → C

Claramente, queremos tomar el camino más pequeño al intentar ver el grado de conexión entre dos personas en la red social.

Hasta aquí todo bien.

Antes de continuar, veamos la complejidad de este problema. Como se dijo antes, Facebook tiene alrededor de 2,07 mil millones de usuarios en el tercer trimestre de 2017. Eso significa que nuestro gráfico tendrá alrededor de 2,07 mil millones de nodos y al menos (2,07 mil millones - 1) bordes (si cada persona tiene al menos un amigo) .

Esta es una escala enorme para resolver este problema. Además, también vimos que puede haber múltiples caminos para llegar desde un vértice de origen determinado hasta un vértice de destino en el gráfico y queremos que el más corto resuelva nuestro problema.

Veremos dos algoritmos clásicos de recorrido de gráficos para resolver nuestro problema:

1. Búsqueda en profundidad y

2. Primera búsqueda en amplitud.

Primera búsqueda en profundidad

Imagina que te quedas atrapado en un laberinto como este.

Tienes que salir de alguna manera. Puede haber varias rutas desde su posición inicial hasta la salida. El enfoque natural para salir del laberinto es probar todos los caminos.

Digamos que tiene dos opciones en el punto en el que se encuentra actualmente. Obviamente, no sabes cuál sale del laberinto. Entonces decides tomar la primera decisión y seguir adelante en el laberinto.

Sigues haciendo movimientos y sigues avanzando y llegas a un callejón sin salida. Ahora lo ideal sería probar una ruta diferente, por lo que retrocede a un punto de control anterior donde tomó una de las opciones y luego prueba una nueva, es decir, una ruta diferente esta vez.

Sigue haciendo esto hasta que encuentres la salida.

Probar de forma recursiva una ruta específica y retroceder son los dos componentes que forman el algoritmo de búsqueda en profundidad (DFS).

Si modelamos el problema del laberinto como un gráfico, los vértices representarían la posición del individuo en el laberinto y los bordes dirigidos entre dos nodos representarían un solo movimiento de una posición a otra. Usando DFS, el individuo probaría todas las rutas posibles hasta que encuentre la salida.

Aquí hay un pseudocódigo de muestra para el mismo.

1 procedure DFS(G,v):2 label v as discovered3 for all edges from v to w in G.adjacentEdges(v) do4 if vertex w is not labeled as discovered then5 recursively call DFS(G,w)

Para profundizar en este algoritmo, consulte: -

Análisis profundo de un gráfico: DFS Traversal

Para bien o para mal, siempre hay más de una forma de hacer algo. Por suerte para nosotros, en el mundo del software y… medium.com

Complejidad del tiempo: O (V + E)

Amplitud primera búsqueda

Imagínese una enfermedad contagiosa que se extiende gradualmente por una región. Todos los días, las personas que padecen la enfermedad infectan a personas nuevas con las que entran en contacto físico. De esta manera, la enfermedad está haciendo una especie de búsqueda de amplitud primero (BFS) entre la población. La "cola" es el conjunto de personas que se acaban de infectar. El gráfico es la red de contactos físicos de la región.

Imagine que necesita simular la propagación de la enfermedad a través de esta red. El nodo raíz de la búsqueda es el paciente cero, el primer paciente conocido de la enfermedad. Empiezas solo con ellos con la enfermedad y con nadie más.

Ahora iteras sobre las personas con las que están en contacto. Algunos contraerán la enfermedad. Ahora repita sobre todos ellos. Proporcione también a las personas que están en contacto con la enfermedad, a menos que ya la hayan tenido. Continúe hasta que haya infectado a todos o haya infectado a su objetivo. Entonces ya terminaste. Así es como funciona la búsqueda en amplitud.

El algoritmo de búsqueda BFS explora los vértices capa por capa, comenzando en el primer vértice y solo avanzando a la siguiente capa una vez que se hayan procesado todos los vértices de la capa actual.

Aquí hay un pseudocódigo de muestra para BFS.

1 procedure BFS(G, v):2 q = Queue()3 q.enqueue(v)4 while q is not empty:5 v = q.dequeue()6 if v is not visited:7 mark v as visited (// Process the node)8 for all edges from v to w in G.adjacentEdges(v) do9 q.enqueue(w)

Para una comprensión más profunda de BFS, consulte este artículo.

Complejidad del tiempo: O (V + E)

Caminos más cortos

Avancemos y resolvamos nuestro problema original: encontrar el camino más corto entre dos vértices dados en un gráfico no dirigido.

Looking at the time complexities of the two algorithms, we can’t really make out the difference between the two for this problem. Both the algorithms will find a path (or rather the shortest path) to our destination from the given source.

Let’s look at the following example.

Suppose we want to find out the shortest path from the node 8 to 10. Let’s look at the nodes that DFS and BFS explore before reaching the destination.

DFS

  • Process 8 → Process 3 → Process 1.
  • Backtrack to 3.
  • Process 6 → Process 4.
  • Backtrack to 6.
  • Process 7.
  • Backtrack to 6 → Backtrack to 3 → Backtrack to 8.
  • Process 10.

A total of 7 nodes are being processed here before the destination is reached. Now let’s look at how BFS does things.

BFS

  • Process 8 → Enqueue 3, 10
  • Process 3 → Enqueue 1,6
  • Process 10.

Woah, that was fast! Just 3 nodes had to be processed and we were at our destination.

The explanation for this speedup that we can see in BFS and not in DFS is because DFS takes up a specific path and goes till the very end i.e. until it hits a dead end and then backtracks.

This is the major downfall of the DFS algorithm. It might have to expand 1000s of levels (in a huge network like that of Facebook, just because it selected a bad path to process in the very beginning) before reaching the path containing our destination. BFS doesn’t face this problem and hence is much faster for our problem.

Additionally, even if DFS finds out the destination, we cannot be sure that the path taken by DFS is the shortest one. There might be other paths as well.

That means that in any case, for the shortest paths problem, DFS would have to span the entire graph to get the shortest path.

In the case of BFS, however, the first occurrence of the destination node ensures that it is the one at the shortest distance from the source.

Conclusion

So far we discussed the problem of Friends Recommendation by Facebook and we boiled it down to the problem of finding the degree of connections between two users in the network graph.

Then we discussed two interesting Graph Traversal algorithms that are very commonly used. Finally, we looked at which algorithm performs the best for solving our problem.

Breadth First Search is the algorithm you want to use if you have to find the shortest distance between two nodes in an undirected, unweighted graph.

Let’s look at this fun problem to depict the difference between the two algorithms.

Assuming that you’ve read the problem statement carefully, let’s try and model this as a graph problem in the first place.

Let all possible strings become nodes in the graph and we have an edge between two vertices if they have a single mutation between them.

Easy, right?

We are given a starting string (read source vertext) eg:- “AACCGGTT” and we have to reach the destination string (read destination vertex) “AACCGGTA” in minimum number of mutations (read minimum number of steps) such that all intermediate strings (nodes) should belong to the given word bank.

Try and solve this problem on your own before looking at the solution below.

If you try to solve it using DFS, you will surely come up with a solution, but there is a test case(s) that will exceed the allotted time limit on the LeetCode platform. That’s because of the problem described before as to why DFS takes so long (process 7 nodes as opposed to 3 in BFS) to reach the destination vertex.

Hope you got the main idea behind the two main graph traversals, and the difference between them when the application is shortest paths in an undirected unweighted graph.

Please recommend (❤) this post if you think this may be useful for someone!