Μια ευγενής εισαγωγή στις δομές δεδομένων: Πώς λειτουργούν τα γραφήματα

Ποιος λοιπόν θέλει να εργαστεί στο Google, στο Facebook ή ίσως στο LinkedIn; Πέρα από την εξαντλητική διαδικασία συνέντευξής τους, ένα κοινό πράγμα που έχουν όλες αυτές οι εταιρείες είναι η μεγάλη τους εξάρτηση από τη δομή των δεδομένων γραφημάτων.

Αφού μάθετε λίγο για τα γραφήματα, θα καταλάβετε γιατί. Μέχρι το τέλος αυτής της ανάρτησης, θα νιώσετε πιο άνετα να μεταβείτε στη συνέντευξη Cracking the Coding - ή σε ένα παρόμοιο βιβλίο προετοιμασίας συνέντευξης - και να χτυπήσετε μερικά προβλήματα εξάσκησης αλγορίθμων δικτύου.

Πώς λειτουργούν τα γραφήματα

Τα γραφήματα είναι μια ισχυρή και ευέλικτη δομή δεδομένων που σας επιτρέπει εύκολα να αντιπροσωπεύσετε πραγματικές σχέσεις μεταξύ διαφορετικών τύπων δεδομένων (κόμβοι). Υπάρχουν δύο κύρια μέρη ενός γραφήματος:

  • Οι κορυφές (κόμβοι) όπου αποθηκεύονται τα δεδομένα, δηλαδή οι αριθμοί στην εικόνα στα αριστερά
  • Οι άκρες (συνδέσεις) που συνδέουν τους κόμβους, δηλαδή οι γραμμές μεταξύ των αριθμών στην εικόνα

Γραφήματα μπορεί να μη κατευθυνόμενη ή κατευθύνονται . Χρησιμοποιώντας το παραπάνω γράφημα ως παράδειγμα - και αντιμετωπίζοντας τις άκρες ως καθημερινές σχέσεις - εδώ είναι η διαφορά:

Άμεσο γράφημα: Εάν ο 6 ήταν φίλος του 4, ο 4 θα ήταν επίσης φίλος του 6. Η σχέση υπάρχει και στις δύο κατευθύνσεις.

Κατευθυνόμενο γράφημα: εάν το 6 είχε μια συντριβή στο 4, αυτό δεν σημαίνει απαραίτητα ότι το 4 πρέπει να έχει μια συντριβή στο 6. Η αγάπη είναι δύσκολη; Οι σχέσεις βασίζονται στην κατεύθυνση των άκρων. Μπορεί να β ε ένας τρόπος σχέση o r μια αμφίδρομη σχέση, αλλά πρέπει να αναφέρεται ρητά.

Ακολουθούν ορισμένες κοινές λειτουργίες που μπορείτε να εκτελέσετε σε γραφήματα:

Προσθήκες

  • addNode: προσθέτει κορυφές στο γράφημα σας
  • addEdge: δημιουργεί άκρα μεταξύ δύο δεδομένων κορυφών στο γράφημα σας

Καταργήσεις

  • removeNode: αφαιρεί κορυφές από το γράφημα σας
  • removeEdge: αφαιρεί τα άκρα μεταξύ δύο δεδομένων κορυφών στο γράφημα σας

Αναζήτηση

  • contains: ελέγχει εάν το γράφημα περιέχει μια δεδομένη τιμή
  • hasEdge: ελέγχει εάν υπάρχει σύνδεση μεταξύ δύο δεδομένων κόμβων στο γράφημα σας

Εκτός από αυτό, τα γραφήματα μπορούν να σταθμίζονται ή να μην σταθμίζονται . Αυτό σημαίνει ότι υπάρχει κάποια αξία ή κόστος που σχετίζεται με τις ακμές μεταξύ των κορυφών. Το καλύτερο παράδειγμα αυτού θα ήταν οι χάρτες google.

Όπως μπορείτε να δείτε, υπάρχουν δύο προτεινόμενες διαδρομές μεταξύ Βομβάη και Δελχί. Αλλά πώς θα γνωρίζει ένας αλγόριθμος γραφήματος Google ότι ένας με μπλε χρώμα είναι η καλύτερη επιλογή; Απλός. Δίνετε στα διαφορετικά δρομολόγια (άκρα) βάρη ισοδύναμα με τις αποστάσεις τους. Γνωρίζοντας αυτό, ο αλγόριθμος μπορεί να συμπεράνει ότι η μία διαδρομή είναι 50 χιλιόμετρα μικρότερη από την άλλη και πιθανώς πιο γρήγορη.

Φυσικά, υπάρχουν και άλλοι παράγοντες δεδομένου του βάρους, όπως καθυστερήσεις και όρια ταχύτητας. Αλλά η ιδέα παραμένει η ίδια. Τα σταθμισμένα γραφήματα σάς επιτρέπουν να επιλέξετε τη γρηγορότερη διαδρομή ή τη διαδρομή με λιγότερη αντίσταση (βλ. Αλγόριθμος Dijkstra).

Όπως μπορείτε να δείτε από αυτά τα παραδείγματα, τα γραφήματα μπορούν να δείχνουν σχεδόν κάθε τύπο σχέσης με απλά δεδομένα και άκρα. Γι 'αυτό τα γραφήματα έχουν χρησιμοποιηθεί τόσο ευρέως από εταιρείες όπως το LinkedIn, το Google και το Facebook. Απλώς διαβάστε αυτήν την ανάρτηση από το Facebook σχετικά με το γιατί έκαναν τη μετάβαση το 2007 από σχεσιακές βάσεις δεδομένων σε βάσεις δεδομένων γραφημάτων.

Τώρα που έχετε μια βασική κατανόηση των γραφημάτων, ας διερευνήσουμε μερικά παραδείγματα.

Παράδειγμα Θήκες Χρήσης:

  • Εκπροσώπηση ενός κοινωνικού δικτύου
  • Αναπαράσταση χαρτών
  • Σκοτώνοντας ερωτήσεις συνέντευξης

Το τελευταίο εξαρτάται από εσάς. Εάν ετοιμάζεστε για συνέντευξη κωδικοποίησης, έχω συμπεριλάβει μερικούς χρήσιμους πρόσθετους πόρους στο τέλος αυτής της ανάρτησης.

Εν τω μεταξύ, ας ρίξουμε μια ματιά στα κοινωνικά δίκτυα.

Δημιουργία κοινωνικού δικτύου χρησιμοποιώντας γραφήματα

Δεδομένου ότι το Facebook έχει το μονοπώλιο σε αυτό το όλο κοινωνικό δίκτυο, τι γίνεται με τη δημιουργία ενός ιδιωτικού κοινωνικού δικτύου για προγραμματιστές; DevBook! Φυσικά, θα μπορούσαμε να κρατήσουμε τα πράγματα απλά και απλά να δημιουργήσουμε μια ομάδα Facebook αντί… Όμως, ως προγραμματιστές βαθμού Α που αγαπούν μια καλή πρόκληση, ας πάρουμε μια περήφανη στιγμή για να ρίξουμε το "KISS" έξω από το παράθυρο.

Αρχικά δημιουργείτε τον χώρο αποθήκευσης για το γράφημα σας. Συνειδητοποιείτε ότι υπάρχουν πιθανώς πολλοί τρόποι με τους οποίους μπορείτε να αντιπροσωπεύσετε μια δομή δεδομένων γραφήματος, αλλά προς το παρόν αποφασίζετε μια λίστα που θα αποθηκεύει κάθε μοναδικό προγραμματιστή ως κλειδί και όλες τις συνδέσεις του ως τις σχετικές τιμές. Όταν εκτελείτε μια γρήγορη αναζήτηση στο Google, συνειδητοποιείτε ότι δημιουργείτε μια λίστα γειτνίασης.

Προτιμάτε να ακολουθείτε ένα λειτουργικό μοτίβο, οπότε αποφασίζετε να ακολουθήσετε την παρακάτω διαδρομή:

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

Τώρα που έχετε την αναπαράσταση γραφήματος, πρέπει να δημιουργήσετε έναν τρόπο να προσθέσετε προγραμματιστές στο γράφημα κατά την εγγραφή τους και να αποθηκεύσετε τυχόν μελλοντικές συνδέσεις που ενδέχεται να έχουν.

Αποφασίζετε να κάνετε τα κλειδιά των χρηστών στο αντικείμενο και να χρησιμοποιήσετε ένα αντικείμενο με μια ιδιότητα άκρων για να διατηρήσετε μια λίστα με τις συνδέσεις τους.

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

Σημειώστε ότι στην πράξη, θα θέλατε να αποθηκεύσετε εγγραφές με μοναδικά αναγνωριστικά χρήστη αντί για ονόματα που δεν θα μπορούσαν να αντικατασταθούν από άλλους χρήστες με το ίδιο όνομα, αλλά έχω χρησιμοποιήσει τα ονόματα των διάσημων προγραμματιστών (συν τον εαυτό μου) για γεύση.

Τώρα μπορείτε να δημιουργήσετε μια containsμέθοδο για να ελέγξετε εάν ένας χρήστης έχει ήδη αποθηκευτεί στο γράφημα σας και να αποτρέψετε την αντικατάσταση οποιασδήποτε από τις σχέσεις που δημιουργούνται καθώς μεγαλώνει ο ιστότοπος.

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 κάνει σπουδαία δουλειά στο πώς να εφαρμόσει μια μηχανή προτάσεων με μια δομή δεδομένων γραφημάτων εδώ. Σίγουρα αξίζει να διαβάσετε, καθώς εφαρμόζει πολλές από τις έννοιες που δεν φτάσαμε εδώ.
  • Για όσους από εσάς είστε εξοικειωμένοι με σχεσιακές βάσεις δεδομένων όπως η MySQL - υπάρχει μια βάση δεδομένων Graph Neo4j, την οποία αγαπώ απολύτως, η οποία όχι μόνο χρησιμοποιεί σύνταξη τύπου SQL, αλλά έχει ένα φοβερό γραφικό περιβάλλον εργασίας χρήστη.