Лагідний вступ до структур даних: як працюють графіки

Тож хто хоче працювати в Google, Facebook чи, можливо, LinkedIn? Окрім процесу виснажливих співбесід, спільним для всіх цих компаній є їхня велика залежність від структури даних графіків.

Дізнавшись трохи про графіки, ви зрозумієте, чому. Наприкінці цього допису вам буде зручніше перейти до програми Cracking the Coding Interview - або подібної підготовчої книги до співбесіди - і вибити деякі практичні проблеми алгоритмів обходу мережі.

Як працюють графіки

Графіки - це потужна та універсальна структура даних, яка легко дозволяє представити реальні взаємозв'язки між різними типами даних (вузлами). Є дві основні частини графіку:

  • Вершини (вузли), де зберігаються дані, тобто цифри на зображенні зліва
  • Краї (з'єднання), які з'єднують вузли, тобто лінії між цифрами на зображенні

Графіки можуть бути ненаправленими або спрямованими . Використовуючи наведений вище графік як приклад - і обробляючи краї як щоденні відносини - ось різниця:

Неспрямований графік: Якби 6 був другом 4, 4 також був би другом 6. Відносини існували в обох напрямках.

Спрямований графік: якщо 6 влюбився в 4, це не обов'язково означає, що 4 повинен впасти в 6. В любові важко? Відносини базуються на напрямку ребер. Це може б е один спосіб ставлення про р двосторонніх відносин а, але це повинно бути чітко зазначено.

Ось декілька типових операцій, які можна виконувати на графіках:

Доповнення

  • addNode: додає вершини до вашого графіку
  • addEdge: створює ребра між двома заданими вершинами на вашому графіку

Видалення

  • removeNode: видаляє вершини з вашого графіка
  • removeEdge: видаляє ребра між двома заданими вершинами у вашому графіку

Пошук

  • contains: перевіряє, чи містить ваш графік задане значення
  • hasEdge: перевіряє, чи існує зв’язок між двома заданими вузлами у вашому графіку

На додаток до цього графіки можуть бути зваженими або незваженими. Все це означає, що між ребрами між ребрами є певна цінність або вартість. Найкращим прикладом цього можуть бути карти Google.

Як бачите, між Мумбаї та Делі є два запропоновані маршрути. Але звідки алгоритм графіків Google може знати, що найкращим варіантом є синій? Простий. Ви даєте різним вагам маршрутів (ребер) ваги, еквівалентні їх відстані. Знаючи це, алгоритм може зробити висновок, що один шлях на 50 км коротший за інший, і, можливо, швидший.

Звичайно, є й інші фактори, що надають вагу, такі як затримки та обмеження швидкості. Але концепція залишається незмінною. Зважені графіки дозволяють вибрати найшвидший шлях або шлях найменшого опору (див. Алгоритм Дейкстри).

Як видно з цих прикладів, графіки можуть відображати майже будь-який тип взаємозв'язку лише з даними та ребрами. Ось чому графіки стали настільки широко використовуватися такими компаніями, як LinkedIn, Google та Facebook. Просто прочитайте цю публікацію Facebook про те, чому вони здійснили перехід ще в 2007 році від реляційних баз даних до баз даних графіків.

Тепер, коли ви добре знаєте, що таке графіки, давайте розглянемо кілька прикладів.

Приклади випадків використання:

  • Представлення соціальної мережі
  • Представлення карт
  • Запитувальні інтерв’ю

Останній там залежить від вас. Якщо ви готуєтесь до співбесіди з кодування, я додав корисні додаткові ресурси в кінці цього допису.

Тим часом, давайте вдаримося в соціальні мережі.

Побудова соціальної мережі за допомогою графіків

Оскільки Facebook має монополію на цілі соціальні мережі, як щодо створення приватної соціальної мережі для розробників? DevBook! Звичайно, ми могли б зробити все просто і замість цього просто створити групу у Facebook ... Але, будучи розробниками класу A, які люблять хороший виклик, давайте скористаємось гордим моментом, щоб викинути “ПОЦІЛУВАННЯ” у вікно.

Спочатку ви створюєте сховище для вашого графіка. Ви розумієте, що існує, мабуть, декілька способів представити структуру даних графіків, але наразі ви вирішуєте список, який зберігатиме кожного унікального розробника як ключ, а всі його зв’язки - як пов’язані з ними значення. Після швидкого пошуку в 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 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.