Implementando Grafo (Graph) com NodeJS e Javascript

Modelar “quem conecta com quem” com objeto aninhado vira spaghetti rápido — rede social, recomendação ou rota no mapa pedem grafo. Este episódio monta uma lista de adjacência em JavaScript/Node.js, base pra BFS e DFS no ep. 14.

O que você vai aprender:

• Diferença entre grafo dirigido e não dirigido (e aresta com peso)
• Implementar vértices e vizinhos com estrutura simples em JS
• Quando lista de adjacência ganha de matriz de adjacência
• Onde grafos aparecem em produto (rede, mapa, recomendação)

Pré-requisitos: árvores (ep. 6) e o resumo da série.

Grafos em JavaScript: lista de adjacência na prática

Grafos são uma estrutura de dados essencial que permite representar relações complexas entre elementos, como redes sociais, sistemas de navegação e otimização de rotas. Aqui vamos abordar a implementação e conceitos básicos dos grafos em NodeJS/JavaScript, vamos tentar trazer insights valiosos.

Implementação

A Teoria

Aqui você vai lembrar muito de árvores (Trees) porque o grafo é uma coleção de nós (ou vértices) e arestas que conectam pares desses nós. Grafos podem ser dirigidos ou não dirigidos e podem incluir arestas com pesos, que oferecem uma representação de custo ou distância entre os nós... sim começa a ficar um pouco mais complexo mas vamos tentar simplificar essa parada ai.

A Prática

Bora pro código então, uma versão básica de grafos precisa ter o número de nós que o grafo tem, e seus nós (sua lista de nós):

class Graph {
  constructor() {
    this.numberOfNodes = 0
    this.adjacentList = {}
  }
}

Parece mais complicado do que é, mas é isso ai. Acabou...brinks! Bora adicionar outras funções pra deixar mais claro:

class Graph {
  constructor() {
    this.numberOfNodes = 0
    this.adjacentList = {}
  }
  add(node) {
    this.adjacentList[node] = []
    this.numberOfNodes++
  }
  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2)
    this.adjacentList[node2].push(node1)
  }
  showConnections() {
    const all = Object.keys(this.adjacentList)
    for (let node of all) {
      let nodeConnections = this.adjacentList[node]
      let connections = ''
      let vertex
      for (vertex of nodeConnections) {
        connections += vertex + ' '
      }
      console.log(`${node} --> ${connections}`)
    }
  }
}

Explicando alguns pontos:

add(node) {
    this.adjacentList[node] = [];
    this.numberOfNodes++;
}

No código acima a gente adiciona um item no grafo, mas preta atenção, mesmo que o nome seja adjacentList na realidade a gente esta com um objeto. Quando adicionamos no adjacentList[node] a gente cria um elemento novo e esse elemento recebe um array vazio de valor, porque não tem conexões com outros elementos.

 addEdge(node1, node2) {
    this.adjacentList[node1].push(node2);
    this.adjacentList[node2].push(node1);
}

Pra adicionar um edge, a gente precisa dizer que esse egde vai conectar os elementos X e Y. Por isso temos o node1 e node2, são os elementos que a edge vai conectar. Quando a gente adiciona uma edge a gente tem que fazer ida e volta, ou seja, adiconar um edge de X para Y e de Y para X, por isso temos 2 pushs que são inversos.

Nesse caso fazemos isso porque não é um grafo direcionado (onde a edge vai só de X para Y e não volta) e também não temos peso nas edges, mas se precisase seria aqui que colocariamos. Se tiver trabalhando com peso (um grafo de ruas, ou relações de amizades em rede social por exemplo) poderiamos por um peso dessa forma (mais ou menos):

addEdge(node1, node2, weight = 0) {
    this.addVertex(node1);
    this.addVertex(node2);
    this.vertices[node1].push({ node: node2, weight });
    this.vertices[node2].push({ node: node1, weight });
}

Testando:

const myGraph = new Graph()
myGraph.add(0)
myGraph.add(1)
myGraph.add(2)
myGraph.add(3)
myGraph.addEdge(0, 2)
myGraph.addEdge(1, 2)
myGraph.addEdge(1, 3)
myGraph.addEdge(2, 3)
myGraph.showConnections()

Rodando isso no seu console, vc deve receber algo nessas linhas:

0 --> 2
1 --> 2 3
2 --> 0 1 3
3 --> 1 2

Isso representa:

• 0 tem conexão com o 2.
• 1 tem conexão com o 2 e com o 3.
• 2 tem conexão com o 0, 1 e com o 3.
• 3 tem conexão com 1 e com o 2.

Essas informações te lembram algo? 👀

Aonde Você Pode Usar/Ver

Aqui não temos muito pra onde fugir, os melhores exemplos são:

Redes Sociais

Grafos são ideais para modelar redes sociais, permitindo representar usuários como vértices e suas conexões ou relações como arestas, facilitando análises complexas de rede.

Sistemas de Navegação e Mapas

Em sistemas de navegação, grafos ajudam a calcular rotas ótimas, utilizando algoritmos como Dijkstra ou A* para encontrar o caminho mais curto entre pontos em um mapa.

Mas é lógico que grafos são uma estrutura de dados que pode ser usada pra várias coisas, por exemplo, se você tem um e-commerce você pode ter um grafo que relaciona produtos e o peso ("weight") seria um percentual de que aquele produto é comprado junto a outro produto, então na hora que alguém colocasse algo no carrinho de compras você mostraria um produto recomendado para ser comprado junto onde o percentual fosse alto (maior peso no grafo)... e assim vai...

Edge cases: grafo denso e shift no BFS

Lista de adjacência com Map + array de vizinhos é ótima pra grafos esparsos. Se quase todo vértice conecta com quase todos, a matriz de adjacência pode ser mais simples de consultar — O(V²) de memória, mas lookup O(1).

"Tá Jon, no ep. 14 você usa queue.shift() no BFS. Isso não é lento?"

É. shift() em array é O(n). Em grafo grande, troque por fila com índices (head++) ou deque. O conceito do BFS não muda — só a performance.

TL;DR — Grafo em JS

Próximos passos

• Hash table (ep. 8): lookup por chave quando o grafo não é o modelo certo — Implementando Hash Tables
• BFS e DFS: Conhecendo algoritmos de grafos

Antes de fechar

Já modelou rede, dependências ou recomendação com grafo? Se viu erro no texto ou tem um caso real que não coube aqui, comenta que a gente ajusta.