Una suave introducción a las estructuras de datos: cómo funcionan los gráficos

Entonces, ¿quién quiere trabajar en Google, Facebook o quizás LinkedIn? Más allá de su agotador proceso de entrevistas, una cosa que todas estas empresas tienen en común es su gran dependencia de la estructura de datos gráficos.

Después de aprender un poco sobre gráficos, comprenderá por qué. Al final de esta publicación, se sentirá más cómodo al saltar a Cracking the Coding Interview, o un libro de preparación de entrevistas similar, y resolver algunos problemas de práctica de algoritmos de recorrido de red.

Cómo funcionan los gráficos

Los gráficos son una estructura de datos poderosa y versátil que le permite representar fácilmente las relaciones de la vida real entre diferentes tipos de datos (nodos). Hay dos partes principales de un gráfico:

Los vértices (nodos) donde se almacenan los datos, es decir, los números en la imagen de la izquierda
Los bordes (conexiones) que conectan los nodos, es decir, las líneas entre los números de la imagen.

Los gráficos pueden estar dirigidos o sin dirección . Usando el gráfico anterior como ejemplo, y tratando los bordes como relaciones cotidianas, aquí está la diferencia:

Gráfico no dirigido: si 6 fuera amigo de 4, 4 también sería amigo de 6. La relación existe en ambas direcciones.

Gráfico dirigido: si 6 estaba enamorado de 4, eso no significa necesariamente que 4 tenga que estar enamorado de 6. ¿El amor es duro? Las relaciones se basan en la dirección de los bordes. Puede b correo una relación de una manera o r una relación bidireccional, pero debe ser declarado explícitamente.

A continuación, se muestran algunas operaciones comunes que puede realizar en gráficos:

Adiciones

addNode: agrega vértices a su gráfico
addEdge: crea bordes entre dos vértices dados en su gráfico

Mudanzas

removeNode: elimina los vértices de su gráfico
removeEdge: elimina los bordes entre dos vértices dados en su gráfico

Buscar

contains: comprueba si su gráfico contiene un valor dado
hasEdge: comprueba si existe una conexión entre dos nodos dados en su gráfico

Además de esto, los gráficos se pueden ponderar o no. Todo esto significa que hay algún valor o costo asociado con los bordes entre los vértices. El mejor ejemplo de esto serían los mapas de Google.

Como puede ver, hay dos rutas sugeridas entre Mumbai y Delhi. Pero, ¿cómo sabría un algoritmo gráfico de Google que uno en azul es la mejor opción? Simple. Le das a las diferentes rutas (bordes) pesos equivalentes a sus distancias. Sabiendo eso, el algoritmo puede deducir que un camino es 50 km más corto que el otro, y probablemente más rápido.

Por supuesto, hay otros factores a los que se les da peso, como retrasos y límites de velocidad. Pero el concepto sigue siendo el mismo. Los gráficos ponderados le permiten elegir la ruta más rápida o la ruta de menor resistencia (consulte el algoritmo de Dijkstra).

Como puede ver en estos ejemplos, los gráficos pueden mostrar casi cualquier tipo de relación con solo datos y bordes. Es por eso que los gráficos se han vuelto tan utilizados por empresas como LinkedIn, Google y Facebook. Solo lea esta publicación de Facebook sobre por qué hicieron la transición en 2007 de bases de datos relacionales a bases de datos de gráficos.

Ahora que tiene una comprensión básica de lo que son las gráficas, exploremos algunos ejemplos.

Casos de uso de ejemplo:

Representando una red social
Representar mapas
Matar preguntas de la entrevista

El último depende de ti. Si se está preparando para una entrevista de codificación, he incluido algunos recursos adicionales útiles al final de esta publicación.

Mientras tanto, echemos un vistazo a las redes sociales.

Construyendo una red social usando gráficos

Dado que Facebook tiene el monopolio de todo este asunto de las redes sociales, ¿qué tal si creamos una red social privada para desarrolladores? DevBook! Por supuesto, podríamos mantener las cosas simples y simplemente crear un grupo de Facebook en su lugar ... Pero siendo desarrolladores de grado A que aman un buen desafío, tomemos un momento de orgullo para tirar "KISS" por la ventana.

Primero crea el almacenamiento para su gráfico. Se da cuenta de que probablemente hay varias formas de representar una estructura de datos de gráfico, pero por ahora decide una lista que almacenará a cada desarrollador único como una clave y todas sus conexiones como sus valores asociados. Al ejecutar una búsqueda rápida en Google, se da cuenta de que está haciendo una lista de adyacencia.

Prefieres seguir un patrón funcional, por lo que decides seguir la ruta a continuación:

let MakeGraph = () => { // Function that will create our graphs let graph = {}; return graph;}

let devBook = MakeGraph(); // Our graph representing our site

Ahora que tiene la representación del gráfico, debe crear una forma de agregar desarrolladores al gráfico cuando se registren y almacenar las conexiones futuras que puedan tener.

Decide hacer las claves de los usuarios en el objeto y usar un objeto con una propiedad de bordes para mantener una lista de sus conexiones.

let MakeGraph = () => { let graph = {};

 graph.addVertex = (node) => { // add members as vertices here // store their connections as properties on an edges object graph[node] = {edges:{}}; }

 return graph;}

let devBook = MakeGraph();

devBook.addVertex('James Gosling');devBook.addVertex('Guido Rossum');devBook.addVertex('Linus Torvalds');devBook.addVertex('Michael Olorunnisola');

// Your graph will now look like this:

{ addVertex: [Function], 'James Gosling': { edges: {} }, 'Guido Rossum': { edges: {} }, 'Linus Torvalds': { edges: {} }, 'Michael Olorunnisola': { edges: {} } }

Tenga en cuenta que, en la práctica, querrá almacenar registros con identificaciones de usuario únicas en lugar de nombres que no puedan ser sobrescritos por otros usuarios con el mismo nombre, pero he usado los nombres de programadores famosos (más yo) para darle sabor.

Ahora puede crear un containsmétodo para comprobar si un usuario ya se ha almacenado en su gráfico y evitar la sobrescritura de cualquiera de las relaciones que se crean a medida que crece el sitio.

let MakeGraph = () => { let graph = {};

 graph.contains = (node)=> { // you can check whether a user exists return !!graph[node]; }

 graph.addVertex = (node) => { if(!graph.contains(node)){ // call contains to prevent overwrite graph[node] = {edges:{}}; } }

return graph;}

Great! Now that you have a good set of unique users, you want to let them connect with each other by creating friendships with each other (edges). These edges won’t be directed, as you realize friendships don’t really work that way.

let MakeGraph = () => { let graph = {};

 graph.contains = (node)=> { return !!graph[node]; }

 graph.addVertex = (node) => { if(!graph.contains(node)){ graph[node] = {edges:{}}; } }

 graph.addEdge = (startNode, endNode) => { // Only if both nodes exist // Add each node to the others edge list

 if(graph.contains(startNode) && graph.contains(endNode)){ graph[startNode].edges[endNode] = true; graph[endNode].edges[startNode] = true; } }

 return graph;}

let devBook = MakeGraph(); // Our graph representing our site

devBook.addVertex('James Gosling');devBook.addVertex('Guido Rossum');devBook.addVertex('Linus Torvalds');devBook.addVertex('Michael Olorunnisola');

// We'll add the edges here!

devBook.addEdge('James Gosling', 'Guido Rossum');devBook.addEdge('Linus Torvalds', 'Michael Olorunnisola');

// Now our devBook will look like this:

{ contains: [Function], addVertex: [Function], addEdge: [Function], 'James Gosling': { edges: { 'Guido Rossum': true } }, 'Guido Rossum': { edges: { 'James Gosling': true } }, 'Linus Torvalds': { edges: { 'Michael Olorunnisola': true } }, 'Michael Olorunnisola': { edges: { 'Linus Torvalds': true } } }

This is absolutely fantastic, but at some point Linus reaches out to you and says, “I have no idea who the Michael guy is. I assumed he was Michael Tiemann, but I finally bothered trying to read his last name.”

Right now you don’t have a way to remove a relationship, so you hop right into the code to whip together a removeEdge method to allow Linus to keep his friends list accurate.

let MakeGraph = () => { let graph = {};

 graph.contains = (node)=> { return !!graph[node]; }

 graph.addVertex = (node) => { if(!graph.contains(node)){ graph[node] = {edges:{}}; } }

 graph.addEdge = (startNode, endNode) => { if(graph.contains(startNode) && graph.contains(endNode)){ graph[startNode].edges[endNode] = true; graph[endNode].edges[startNode] = true; } } graph.removeEdge = (startNode, endNode) => { if(graph.contains(startNode) && graph.contains(endNode)){ delete graph[startNode].edges[endNode] delete graph[endNode].edges[startNode] } }

 return graph;}

devBook.removeEdge('Linus Torvalds', 'Michael Olorunnisola');

// Relationship removed!

{ contains: [Function], addVertex: [Function], addEdge: [Function], removeEdge: [Function], 'James Gosling': { edges: { 'Guido Rossum': true } }, 'Guido Rossum': { edges: { 'James Gosling': true } }, 'Linus Torvalds': { edges: {} }, 'Michael Olorunnisola': { edges: {} } }

Great! Unfortunately Linus says that he just wanted to try the site out, but that he’s way to0 hermitic to be on a site like this. He really wants to delete his account, but is currently unable to because you haven’t added a node removal method yet.

let MakeGraph = () => { let graph = {};

 graph.contains = (node)=> { return !!graph[node]; }

 graph.addVertex = (node) => { if(!graph.contains(node)){ graph[node] = {edges:{}}; } }

 graph.removeVertex = (node) => { if(graph.contains(node)) { // We need to remove any existing edges the node has for(let connectedNode in graph[node].edges) { graph.removeEdge(node, connectedNode); } delete graph[node]; }

 graph.addEdge = (startNode, endNode) => { if(graph.contains(startNode) && graph.contains(endNode)){ graph[startNode].edges[endNode] = true; graph[endNode].edges[startNode] = true; } } graph.removeEdge = (startNode, endNode) => { if(graph.contains(startNode) && graph.contains(endNode)){ delete graph[startNode].edges[endNode] delete graph[endNode].edges[startNode] } }

return graph;}

// Now we can remove users!

devBook.removeVertex('Linus Torvalds');

Great job! Although you lost a potentially valuable user, you’ve been able to implement a basic graph system to keep track of all of your users and their friendships.

If you notice, we didn’t implement the hasEdge method, but I think you have enough information to give it a shot! Feel free to include your implementation in the comments below ?.

A time complexity analysis on the graph methods as an adjacency list

Here’s our code again:

let MakeGraph = () => { let graph = {};

 graph.contains = (node)=> { return !!graph[node]; }

 graph.addVertex = (node) => { if(!graph.contains(node)){ graph[node] = {edges:{}}; } }

 graph.removeVertex = (node) => { if(graph.contains(node)) { for(let connectedNode in graph[node].edges) { graph.removeEdge(node, connectedNode); } delete graph[node]; } }

 graph.addEdge = (startNode, endNode) => { if(graph.contains(startNode) && graph.contains(endNode)){ graph[startNode].edges[endNode] = true; graph[endNode].edges[startNode] = true; } } graph.removeEdge = (startNode, endNode) => { if(graph.contains(startNode) && graph.contains(endNode)){ delete graph[startNode].edges[endNode] delete graph[endNode].edges[startNode] } }

 return graph;}

addNodeis O(1): You’re just creating a property on an object so it’s constant time

addEdgeis O(1): Since you’re using an object to represent your graph, it’s a constant time operation since your nodes and edges are represented as properties.

removeNodeis O(n): If a node has edges, you’re going to have to iterate over all it’s existing edges to remove it’s existence as an edge on it’s connected nodes.

removeEdgeis O(1): Since your nodes are properties on your graph, you can access them in constant time and just delete the edges which are also accessible in constant time.

containsis O(1): As a property on your graph, it’s a constant time lookup for a node.

hasEdgeis O(1): Both nodes would be properties on your graph, so it would be a constant time lookup.

Time for a quick recap

Graphs:

are just a combination of vertices and edges representing data and relationships
have addNode, addEdge, removeNode, and removeEdge methods to manage their contents
have a contains and a hasEdge method to help you track the state of their state

Cómo funcionan los gráficos

Construyendo una red social usando gráficos

A time complexity analysis on the graph methods as an adjacency list

Time for a quick recap

Further Reading