En mild introduktion til datastrukturer: Hvordan grafer fungerer

Så hvem vil arbejde hos Google, Facebook eller måske LinkedIn? Ud over deres udmattende interviewproces er en ting, som alle disse virksomheder har til fælles, deres stærke afhængighed af grafdatastrukturen.

Efter at have lært lidt om grafer, forstår du hvorfor. Ved afslutningen af ​​dette indlæg vil du føle dig mere komfortabel med at springe ind i Cracking the Coding Interview - eller en lignende forberedelsesbog til interviews - og slå nogle af netværksgennemgangsproblemer ud.

Sådan fungerer grafer

Grafer er en stærk og alsidig datastruktur, der let giver dig mulighed for at repræsentere forhold i det virkelige liv mellem forskellige datatyper (noder). Der er to hoveddele af en graf:

  • Hovedpunkterne (noder), hvor dataene er gemt, dvs. tallene i billedet til venstre
  • Kanterne (forbindelser), der forbinder noderne, dvs. linjerne mellem tallene i billedet

Grafer kan være ikke-rettet eller rettet . Brug af ovenstående graf som et eksempel - og behandling af kanterne som hverdagsrelationer - her er forskellen:

Ustyret graf: Hvis 6 var en ven af ​​4, ville 4 ligeledes være en ven af ​​6. Forholdet eksisterer i begge retninger.

Regisseret graf: hvis 6 havde en crush på 4, betyder det ikke nødvendigvis, at 4 skal have en crush på 6. Love's tough?. Forholdet er baseret på retningen af ​​kanterne. Det kan b e en enkeltbillet forhold o r en to-vejs forhold, men det skal udtrykkeligt anført.

Her er nogle almindelige operationer, du kan udføre på grafer:

Tilføjelser

  • addNode: tilføjer hjørner til din graf
  • addEdge: opretter kanter mellem to givne hjørner i din graf

Fjernelse

  • removeNode: fjerner hjørner fra din graf
  • removeEdge: fjerner kanter mellem to givne hjørner i din graf

Søg

  • contains: kontrollerer, om din graf indeholder en given værdi
  • hasEdge: kontrollerer, om der findes en forbindelse mellem to givne noder i din graf

Ud over dette kan grafer vægtes eller ikke vejes . Alt dette betyder, at der er en værdi eller pris forbundet med kanterne mellem hjørnerne. Det bedste eksempel på dette ville være google maps.

Som du kan se, er der to foreslåede ruter mellem Mumbai og Delhi. Men hvordan ville en Google-algoritme vide, at en i blå er den bedste mulighed? Enkel. Du giver de forskellige ruter (kanter) vægte svarende til deres afstande. Når man ved det, kan algoritmen udlede, at den ene sti er 50 km kortere end den anden og sandsynligvis hurtigere.

Selvfølgelig er der andre faktorer givet vægt som forsinkelser og hastighedsbegrænsninger. Men konceptet forbliver det samme. Vægtede grafer giver dig mulighed for at vælge den hurtigste sti eller stien med mindst modstand (se Dijkstras algoritme).

Som du kan se fra disse eksempler, kan grafer vise næsten alle typer forhold med kun data og kanter. Dette er grunden til, at grafer er blevet så vidt brugt af virksomheder som LinkedIn, Google og Facebook. Læs bare dette indlæg fra Facebook om, hvorfor de skiftede tilbage i 2007 fra relationsdatabaser til grafdatabaser.

Nu hvor du har en grundlæggende forståelse af, hvad grafer er, lad os undersøge nogle eksempler.

Eksempel på brugstilfælde:

  • Repræsenterer et socialt netværk
  • Repræsenterer kort
  • Dræbte spørgsmål om interview

Den sidste der er op til dig. Hvis du gør dig klar til et kodningssamtale, har jeg inkluderet nogle nyttige yderligere ressourcer i slutningen af ​​dette indlæg.

I mellemtiden, lad os tage et stød på sociale netværk.

Opbygning af et socialt netværk ved hjælp af grafer

Da Facebook slags har monopol på hele denne ting på det sociale netværk, hvad med at skabe et privat socialt netværk til udviklere? DevBook! Selvfølgelig kunne vi holde tingene enkle og bare oprette en Facebook-gruppe i stedet ... Men når vi er klasse A-udviklere, der elsker en god udfordring, lad os tage et stolt øjeblik til at smide "KISS" ud af vinduet.

Først opretter du lageret til din graf. Du er klar over, at der sandsynligvis er flere måder, du kan repræsentere en grafdatastruktur på, men for nu beslutter du en liste, der gemmer hver unik udvikler som en nøgle og alle deres forbindelser som deres tilknyttede værdier. Når du kører en hurtig Google-søgning, indser du, at du laver en nærhedsliste.

Du foretrækker at følge et funktionelt mønster, så du beslutter dig for at gå ruten nedenfor:

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

Nu hvor du har grafrepræsentationen, skal du oprette en måde at tilføje udviklere til grafen, når de tilmelder sig, og at gemme eventuelle fremtidige forbindelser, de måtte have.

Du beslutter dig for at gøre brugerne nøgler til objektet og bruge et objekt med en kantegenskab til at føre en liste over deres forbindelser.

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: {} } }

Bemærk, at i praksis vil du gemme poster med unikke bruger-id'er i stedet for navne, der ikke kunne overskrives af andre brugere med samme navn, men jeg har brugt navnene på berømte programmører (plus mig selv) til smag.

Nu kan du oprette en containsmetode til at kontrollere, om en bruger allerede er blevet gemt på din graf, og forhindre overskrivning af nogen af ​​de forhold, der oprettes, når webstedet vokser.

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:

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

Further Reading

To say that there is a lot more to the graph data structure would be a huge understatement.

You could have represented the edges as an array instead of objects, or the entire graph as a 2-d array (adjacency matrix). You could have even represented the graph solely by their edges in an array (edge list).

As with anything in programming, there are trade-offs associated with each representation and it’s definitely worthwhile learning what they are.

Graphs are by far my favorite data structure and also one of the most versatile, but that’s just my humble opinion. (Those of you who love trees really are just graph lovers in disguise ?).

Maybe I can sway you to love them as much as I do, so here are a few additional resources for you to read up on them:

  • This Wikipedia Article does a great job not only covering the different representation of a graph, but also introducing you to some of the algorithms often associated with graphs.
  • For those of you who are using Python here’s a graph implementation from the Python team!
  • TutorialsPoint does a really good job of diving into how to implement two of the algorithms: Depth First Search and Breadth First Search. You might be confronted with these graph algorithms in interviews.
  • Keith Woods gør et godt stykke arbejde med at gå igennem, hvordan man implementerer en anbefalingsmotor med en grafdatastruktur her. Absolut værd at læse, da det implementerer mange af de begreber, vi ikke kom til her.
  • For dem af jer, der er fortrolige med relationsdatabaser som MySQL - der er en grafdatabase Neo4j, som jeg absolut elsker, der ikke kun bruger SQL-lignende syntaks, men har en fantastisk grafisk brugergrænseflade.