de Michael Olorunnisola

O introducere ușoară a structurilor de date: modul în care funcționează graficele

O introducere usoara a structurilor de date modul in care
Sursă: TheNextWeb

Deci cine vrea să lucreze la Google, Facebook sau poate LinkedIn? Dincolo de procesul lor de interviu istovitor, un lucru pe care toate aceste companii îl au în comun este încrederea lor mare în structura datelor grafice.

După ce ați învățat puțin despre grafice, veți înțelege de ce. Până la sfârșitul acestei postări, vă veți simți mai confortabil săriți în Cracking Interviu de codare – sau o carte similară de pregătire a interviului – și eliminarea unor algoritmi de traversare a rețelei practică probleme.

Cum funcționează graficele

Graficele sunt o structură de date puternică și versatilă care vă permite cu ușurință să reprezentați relațiile din viața reală între diferite tipuri de date (noduri). Există două părți principale ale unui grafic:

O introducere usoara a structurilor de date modul in care
  • Vârfurile (nodurile) în care sunt stocate datele adică numerele din imaginea din stânga
  • Marginile (conexiunile) care conectează nodurile adică liniile dintre numerele din imagine

Graficele pot fi nedirecționat sau regizat. Folosind graficul de mai sus ca exemplu – și tratând marginile ca relații zilnice – iată diferența:

ad-banner

Grafic nedirectat: Dacă 6 ar fi prieten cu 4, 4 ar fi, de asemenea, prieten cu 6. Relația există în ambele direcții.

Grafic direcționat: dacă 6 a avut o îndrăgostire pe 4, asta nu înseamnă neapărat că 4 trebuie să aibă o îndrăgostire pe 6. Iubirea e dură? Relațiile se bazează pe direcția marginilor. Poate bo relație unidirecțională or o relație bidirecțională, dar trebuie menționată în mod explicit.

Iată câteva operații obișnuite pe care le puteți efectua pe grafice:

Adăugări

  • addNode: adaugă vârfuri grafului dvs.
  • addEdge: creează muchii între două vârfuri date în graficul dvs.

Mutări

  • removeNode: elimină vârfurile din grafic
  • removeEdge: elimină muchiile dintre două vârfuri date în graficul dvs.

Căutare

  • contains: verifică dacă graficul dvs. conține o valoare dată
  • hasEdge: verifică dacă există o conexiune între două noduri date din graficul dvs.

În plus, graficele pot fi ponderat sau neponderat. Toate acestea înseamnă că există o anumită valoare sau cost asociată cu marginile dintre vârfuri. Cel mai bun exemplu în acest sens ar fi google maps.

1611573369 216 O introducere usoara a structurilor de date modul in care

După cum puteți vedea, există două rute sugerate între Mumbai și Delhi. Dar cum ar ști un algoritm grafic Google că cel albastru este cea mai bună opțiune? Simplu. Dai diferitelor rute (margini) greutăți echivalente cu distanțele lor. Știind acest lucru, algoritmul poate deduce că o cale este cu 50 km mai scurtă decât cealaltă și probabil mai rapidă.

Desigur, există și alți factori, având în vedere greutatea, cum ar fi întârzierile și limitele de viteză. Dar conceptul rămâne același. Graficele ponderate vă permit să alegeți calea cea mai rapidă sau calea cu cea mai mică rezistență (a se vedea Algoritmul lui Dijkstra).

După cum puteți vedea din aceste exemple, graficele pot arăta aproape orice tip de relație doar cu date și margini. Acesta este motivul pentru care graficele au devenit atât de utilizate pe scară largă de companii precum LinkedIn, Google și Facebook. Doar citiți această postare de Facebook despre motivul pentru care au făcut tranziția în 2007 de la baze de date relaționale la baze de date grafice.

Acum, că aveți o înțelegere de bază despre ce sunt graficele, să explorăm câteva exemple.

Exemple de cazuri de utilizare:

  • Reprezentarea unei rețele sociale
  • Reprezentarea hărților
  • Uciderea întrebărilor interviului

Ultimul depinde de tine. Dacă vă pregătiți pentru un interviu de codare, am inclus câteva resurse suplimentare utile la sfârșitul acestei postări.

Între timp, să luăm o lovitură la rețelele de socializare.

Construirea unei rețele sociale folosind grafice

Întrucât Facebook are un monopol asupra întregului aspect al rețelei sociale, ce zici de noi să creăm o rețea socială privată pentru dezvoltatori? DevBook! Desigur, am putea să simplificăm lucrurile și să creăm un grup Facebook … Însă, fiind dezvoltatori de gradul A care iubesc o provocare bună, să luăm un moment mândru pentru a arunca „KISS” pe fereastră.

1611573369 443 O introducere usoara a structurilor de date modul in care

Mai întâi creați spațiul de stocare pentru graficul dvs. Vă dați seama că există, probabil, mai multe moduri în care puteți reprezenta o structură de date grafice, dar deocamdată decideți o listă care va stoca fiecare dezvoltator unic ca cheie și toate conexiunile lor ca valori asociate. După ce efectuați o căutare rapidă pe Google, vă dați seama că faceți o listă de adiacențe.

Preferați să urmați un model funcțional, deci decideți să parcurgeți ruta de mai jos:

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

Acum că aveți reprezentarea graficului, trebuie să creați o modalitate de a adăuga dezvoltatori la grafic atunci când se înscriu și de a stoca orice conexiuni viitoare pe care le-ar putea avea.

Decideți să creați cheile utilizatorilor pe obiect și să utilizați un obiect cu o proprietate margini pentru a păstra o listă a conexiunilor lor.

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

Rețineți că, în practică, ați dori să stocați înregistrări cu ID-uri de utilizator unice în loc de nume care nu ar putea fi suprascrise de alți utilizatori cu același nume, dar am folosit numele programatorilor celebri (plus eu) pentru gust.

Acum puteți construi un contains metodă pentru a verifica dacă un utilizator a fost deja stocat în graficul dvs. și pentru a preveni suprascrierea oricăreia dintre relațiile create pe măsură ce site-ul crește.

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;}

Grozav! Acum, că aveți un set bun de utilizatori unici, doriți să îi lăsați să se conecteze între ei, creând prietenii între ei (margini). Aceste margini nu vor fi direcționate, deoarece vă dați seama că prieteniile nu funcționează așa.

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

Acest lucru este absolut fantastic, dar la un moment dat Linus ajunge la tine și îți spune: „Habar n-am cine este tipul Michael. Am presupus că este Michael Tiemann, dar în cele din urmă m-am deranjat să încerc să-i citesc numele de familie. ”

În acest moment nu aveți o modalitate de a elimina o relație, așa că treceți direct în cod pentru a bate împreună un removeEdge metodă pentru a-i permite lui Linus să-și păstreze lista de prieteni exactă.

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

Grozav! Din nefericire, Linus spune că a vrut doar să încerce site-ul, dar că este o cale să fie ermit să fie pe un site ca acesta. El dorește cu adevărat să-și șteargă contul, dar în prezent nu poate, deoarece nu ați adăugat încă o metodă de eliminare a nodului.

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');

Buna treaba! Deși ați pierdut un utilizator potențial valoros, ați reușit să implementați un sistem grafic de bază pentru a urmări toți utilizatorii dvs. și prietenia lor.

Dacă observați, nu am implementat hasEdge metoda, dar cred că aveți suficiente informații pentru a da o lovitură! Nu ezitați să includeți implementarea în comentariile de mai jos?

O analiză a complexității timpului pe metodele grafice ca listă de adiacență

Iată codul nostru din nou:

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;}

addNode este O (1): Creați doar o proprietate pe un obiect, deci este timpul constant

addEdge este O (1): Deoarece utilizați un obiect pentru a vă reprezenta graficul, este o operație în timp constant, deoarece nodurile și muchiile dvs. sunt reprezentate ca proprietăți.

removeNode este Pe): Dacă un nod are margini, va trebui să iterați peste toate marginile existente pentru a elimina existența ca margine pe nodurile conectate.

removeEdge este O (1): Deoarece nodurile dvs. sunt proprietăți pe graficul dvs., le puteți accesa în timp constant și pur și simplu ștergeți marginile care sunt, de asemenea, accesibile în timp constant.

contains este O (1): Ca o proprietate pe graficul dvs., este o căutare în timp constant pentru un nod.

hasEdge este O (1): Ambele noduri ar fi proprietăți pe graficul dvs., deci ar fi o căutare în timp constant.

Este timpul pentru o recapitulare rapidă

Grafice:

  1. sunt doar o combinație de vârfuri și margini reprezentând date și relații
  2. avea addNode, addEdge, removeNode, și removeEdge metode de gestionare a conținutului acestora
  3. ia o contains și a hasEdge metodă pentru a vă ajuta să urmăriți starea stării lor

Lecturi suplimentare

A spune că există mult mai mult în structura datelor grafice ar fi o subevaluare imensă.

Ați fi putut reprezenta marginile ca o matrice în loc de obiecte sau întregul grafic ca o matrice 2-d (matricea de adiacență). Ați fi putut chiar să reprezentați graficul numai după marginile lor într-o matrice (lista de margini).

Ca și în orice altceva din programare, există compromisuri asociate fiecărei reprezentări și cu siguranță merită să aflați ce sunt acestea.

Graficele sunt de departe structura mea de date preferată și, de asemenea, una dintre cele mai versatile, dar aceasta este doar umila mea părere. (Cei dintre voi care iubesc copacii sunt doar iubitori de grafice deghizați ?).

Poate că te pot determina să-i iubești la fel de mult ca mine, așa că iată câteva resurse suplimentare pentru a le citi despre ele:

  • Acest Articol Wikipedia face o treabă excelentă nu doar acoperind reprezentarea diferită a unui grafic, ci și prezentându-vă unii dintre algoritmii adesea asociați cu graficele.
  • Pentru aceia dintre voi care utilizează Python, iată un implementarea graficului din echipa Python!
  • Tutoriale Punct face o treabă foarte bună de a se scufunda în modul de implementare a doi dintre algoritmi: Căutare în adâncime și Lățimea întâi căutare. S-ar putea să vă confruntați cu acești algoritmi grafici în interviuri.
  • Keith Woods face o treabă extraordinară prin parcurgerea modului de implementare a unui motor de recomandare cu o structură de date grafice aici. Cu siguranță merită citit, deoarece implementează o mulțime de concepte la care nu am ajuns aici.
  • Pentru cei dintre voi care sunt familiarizați cu bazele de date relaționale precum MySQL – există o bază de date Graph Neo4j, pe care îl iubesc absolut, care nu numai că folosește sintaxă asemănătoare SQL-ului, ci are un aspect minunat interfață grafică de utilizator.