Desvendando Conexões: Grafos
Aprenda a representar grafos e domine os algoritmos de travessia fundamentais: Busca em Largura (BFS) e Busca em Profundidade (DFS).
Árvores são elegantes, mas o mundo real é mais bagunçado. Redes sociais, rotas de voos, o mapa de uma cidade, a própria internet... tudo isso são Grafos. Meu primeiro problema de grafo em uma entrevista pareceu um salto gigantesco de complexidade em relação a árvores.
Mas a verdade é que, uma vez que você entende como representar um grafo e domina as duas formas principais de "caminhar" por ele, a maioria dos problemas se torna muito mais gerenciável.
Tudo se resume a duas ideias: explorar "fundo" primeiro (DFS) ou explorar "largo" primeiro (BFS). Esta aula é sobre te dar o mapa e a bússola para navegar em qualquer problema de grafo que aparecer na sua frente.
1. O que são Grafos? (Árvores sem Regras)
Um Grafo é uma estrutura de dados que consiste em um conjunto de vértices (ou nós) e um conjunto de arestas que conectam pares de vértices. Pense neles como uma generalização de árvores: uma árvore é um tipo de grafo, mas um grafo pode ter ciclos, múltiplos caminhos entre nós e até ser desconectado.
2. Representando Grafos no Código
Antes de atravessar um grafo, precisamos construí-lo. As duas formas mais comuns são a Lista de Adjacência e a Matriz de Adjacência.
Lista de Adjacência (A Mais Comum)
É a forma mais usada em entrevistas. Basicamente, é um mapa (ou objeto) onde cada chave é um vértice, e o valor é um array de seus vizinhos.
// Grafo: A -- B -- C
// | |
// D -- E
const graph = {
'A': ['B', 'D'],
'B': ['A', 'C', 'E'],
'C': ['B'],
'D': ['A', 'E'],
'E': ['B', 'D']
};
// Usando um Map em JS (mais flexível para chaves não-string)
const graphWithMap = new Map();
graphWithMap.set('A', ['B', 'D']);
// etc.Matriz de Adjacência
É uma matriz NxN (onde N é o número de vértices). Se matrix[i][j] for 1, existe uma aresta entre os vértices i e j. É boa para grafos densos, mas gasta muita memória para grafos com poucas conexões (esparsos).
Qual Usar?
3. Atravessando o Grafo: DFS e BFS
"Atravessar" (ou percorrer) um grafo significa visitar todos os seus vértices de forma sistemática. Os dois algoritmos clássicos para isso são a Busca em Profundidade (DFS) e a Busca em Largura (BFS).
DFS (Busca em Profundidade): O Explorador de Labirintos 🧭
O DFS explora o mais fundo possível por um caminho antes de voltar (backtrack). É como entrar em um labirinto e seguir sempre a primeira parede à sua direita até bater em um beco sem saída, para então voltar e tentar o próximo caminho.
Pode ser implementado elegantemente com recursão (que usa a call stack implicitamente) ou iterativamente com uma Pilha (Stack).
function dfsRecursive(graph, startNode, visited = new Set()) {
// 1. Marca o nó atual como visitado para não entrar em loop infinito.
visited.add(startNode);
console.log(startNode); // Processa o nó
// 2. Para cada vizinho do nó atual...
const neighbors = graph[startNode] || [];
for (const neighbor of neighbors) {
// 3. ...se o vizinho ainda não foi visitado, chama a recursão para ele.
if (!visited.has(neighbor)) {
dfsRecursive(graph, neighbor, visited);
}
}
}
// Chamada inicial:
// dfsRecursive(graph, 'A');DFS Iterativo (com Pilha)
A versão iterativa faz a mesma coisa, mas troca a "mágica" da call stack da recursão por uma Pilha (Stack) explícita. O resultado é o mesmo.
function dfsIterative(graph, startNode) {
const stack = [startNode]; // 1. Começa com uma Pilha contendo o nó inicial.
const visited = new Set();
visited.add(startNode);
while (stack.length > 0) {
// 2. Pega o último nó da pilha (LIFO).
const currentNode = stack.pop();
console.log(currentNode); // Processa o nó
// 3. Adiciona os vizinhos não visitados à pilha.
const neighbors = graph[currentNode] || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
stack.push(neighbor);
}
}
}
}BFS (Busca em Largura): A Onda de Propagação 🌊
O BFS explora todos os vizinhos de um nó antes de passar para os vizinhos dos vizinhos. É como uma onda se espalhando a partir de um ponto, visitando tudo em um nível antes de ir para o próximo.
É implementado com uma Fila (Queue).
function bfs(graph, startNode) {
const queue = [startNode]; // 1. Começa com uma Fila contendo o nó inicial.
const visited = new Set(); // 2. Um conjunto para rastrear nós já visitados/enfileirados.
visited.add(startNode);
while (queue.length > 0) {
// 3. Pega o primeiro nó da fila.
const currentNode = queue.shift();
console.log(currentNode); // Processa o nó
// 4. Adiciona todos os vizinhos não visitados ao final da fila.
const neighbors = graph[currentNode] || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
// Chamada inicial:
// bfs(graph, 'A');DFS vs. BFS: O Guia Definitivo para Entrevistas
- Use DFS (Pilha/Recursão) quando:
- A pergunta for simplesmente "existe um caminho entre A e B?".
- Você precisar detectar ciclos em um grafo.
- O problema envolver topologia de ordenação (topological sort).
- Você precisar visitar todos os nós e a ordem não importar tanto.
- Use BFS (Fila) quando:
- A pergunta for "qual o caminho MAIS CURTO entre A e B?" em um grafo não-ponderado. Esta é a aplicação mais famosa e cobrada!
- Você precisar atravessar o grafo por níveis.
💊 Pílula Devly
Árvores são grafos com regras. Grafos são o mundo real. Para navegar, você tem duas lanternas: a DFS, para explorar um caminho até o fim (com uma pilha/recursão), e a BFS, para explorar por camadas (com uma fila). E lembre-se: se a pergunta for "caminho mais curto", a resposta quase sempre é BFS.