Gyengéd bevezetés az adatstruktúrákhoz: Hogyan működnek a grafikonok

Tehát ki akar dolgozni a Google-n, a Facebookon, vagy esetleg a LinkedIn-nél? A fárasztó interjúk folyamata mellett ezekben a vállalatokban egyetlen dolog közös, hogy erősen támaszkodnak a grafikon adatszerkezetére.

Miután kicsit megismerte a grafikonokat, meg fogja érteni, miért. E bejegyzés végére kényelmesebbnek érzi magát, ha belevág a Cracking the Coding Interview-ba - vagy egy hasonló interjú-előkészítő könyvbe -, és kiüt néhány hálózati bejárási algoritmust.

Hogyan működnek a grafikonok

A grafikonok hatékony és sokoldalú adatstruktúra, amely könnyedén lehetővé teszi a valós típusú kapcsolatok ábrázolását a különböző típusú adatok (csomópontok) között. A grafikonnak két fő része van:

  • Az adatokat tároló csúcsok (csomópontok), azaz a bal oldali képen látható számok
  • A csomópontokat összekötő élek (kapcsolatok), azaz a képen lévő számok közötti vonalak

Grafikonok lehet irányítatlan vagy irányított . Például a fenti grafikont használva - és az éleket mindennapi kapcsolatokként kezelve - íme a különbség:

Irányítatlan grafikon: Ha 6 a 4 barátja, akkor a 4 is a 6. barátja. A kapcsolat mindkét irányban létezik.

Irányított grafikon: ha 6-nak 4-en volt összetörése, ez nem feltétlenül jelenti azt, hogy a 4-nek össze kell törnie a 6-at. A kapcsolatok az élek irányán alapulnak. Ez b e egy egyirányú kapcsolat o r kétirányú kapcsolat, de meg kell kifejezetten.

Íme néhány általános művelet, amelyet grafikonokon hajthat végre:

Kiegészítések

  • addNode: csúcsokat ad hozzá a grafikonodhoz
  • addEdge: éleket hoz létre a grafikon két megadott csúcsa között

Költöztetések

  • removeNode: eltávolítja a csúcsokat a gráfból
  • removeEdge: eltávolítja az éleket a grafikon két megadott csúcsa között

Keresés

  • contains: ellenőrzi, hogy a grafikonja tartalmaz-e egy adott értéket
  • hasEdge: ellenőrzi, hogy van-e kapcsolat a grafikon két megadott csomópontja között

Ezen felül a grafikonok lehetnek súlyozottak vagy súlyozatlanok. Mindez azt jelenti, hogy van valami érték vagy költség a csúcsok közötti élekhez. A legjobb példa erre a google maps lenne.

Mint látható, két javasolt útvonal van Mumbai és Delhi között. De honnan tudná a Google grafikonalgoritmusa, hogy a kék színű a legjobb megoldás? Egyszerű. Megadja a különböző útvonalaknak (éleknek) a távolságukkal megegyező súlyát. Ennek tudatában az algoritmus arra következtethet, hogy az egyik út 50 km-rel rövidebb, mint a másik, és valószínűleg gyorsabb is.

Természetesen vannak más tényezők is, mint a késések és a sebességkorlátozások. De a koncepció ugyanaz marad. A súlyozott grafikonok segítségével kiválaszthatja a leggyorsabb vagy a legkisebb ellenállási utat (lásd Dijkstra algoritmusát).

Amint ezekből a példákból látható, a grafikonok szinte bármilyen típusú kapcsolatot mutatnak csak adatokkal és élekkel. Ezért olyan széles körben használták a grafikonokat olyan vállalatok, mint a LinkedIn, a Google és a Facebook. Csak olvassa el a Facebook ezt a bejegyzését arról, hogy miért léptek vissza 2007-ben a relációs adatbázisokról a grafikonos adatbázisokra.

Most, hogy alapvető ismerete van a grafikonokról, vizsgáljunk meg néhány példát.

Példa használati esetekre:

  • Közösségi hálózat képviselete
  • Térképek ábrázolása
  • Interjúk kérdéseinek megölése

Az utolsó ott áll rajtad. Ha készülsz egy kódoló interjúra, a bejegyzés végén néhány hasznos kiegészítő forrást is feltüntettem.

Addig szúrjunk szét a közösségi hálózatokon.

Közösségi hálózat kiépítése grafikonok segítségével

Mivel a Facebook egyfajta monopóliummal rendelkezik ezzel az egész közösségi hálóval kapcsolatban, mi lenne, ha létrehoznánk egy privát közösségi hálózatot a fejlesztők számára? DevBook! Természetesen egyszerűbbé tehetnénk a dolgokat, és csak létrehozhatnánk egy Facebook-csoportot ... De mivel A osztályú fejlesztők vagyunk, akik szeretik a jó kihívást, vegyünk egy büszke pillanatot, hogy kidobjuk a „KISS” -t az ablakon.

Először hozza létre a grafikon tárhelyét. Tisztában van azzal, hogy valószínűleg többféle módon ábrázolhatja a grafikon adatszerkezetét, de egyelőre dönt egy listáról, amely minden egyedi fejlesztőt kulcsként tárol, és minden kapcsolatukat társított értékként tárolja. Gyors Google keresés futtatása után rájön, hogy szomszédsági listát készít.

Inkább funkcionális mintát követ, ezért úgy dönt, hogy az alábbi útvonalat választja:

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

Now that you have the graph representation, you need to create a way to add developers to the graph when they sign up, and to store any future connections they might have.

You decide to make the users keys on the object, and use an object with an edges property to keep a list of their connections.

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

Note that in practice, you would want to store records with unique user id’s instead of names that couldn’t be overwritten by other users with the same name, but I’ve used the names of famous programmers (plus myself) for flavor.

Now you can build a contains method to check whether a user has already been stored on your graph, and prevent the overwriting of any of the relationships that are created as the site grows.

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 does a great job of walking through how to implement a recommendation engine with a graph data structure here. Definitely worth a read, as it implements a lot of the concepts we didn’t get to here.
  • For those of you who are familiar with relational databases like MySQL — there’s a Graph database Neo4j, which I absolutely love, that not only uses SQL-like syntax, but has an awesome graphical user interface.