Algoritmos em Grafos
Grafos modelam virtualmente qualquer sistema complexo de conexões: de redes sociais e malhas viárias a dependências de pacotes e fluxos de transações financeiras. Para um desenvolvedor sênior, o domínio de algoritmos em grafos é fundamental para otimizar buscas complexas, projetar caminhos mínimos de baixa latência e gerenciar dependências. Vamos desmistificar essas estruturas e seus trade-offs clássicos em Java.
A Malha Aérea e a Modelagem de Conexões
Imagine uma companhia aérea global. Cada aeroporto é um vértice (ou nó), e cada voo direto entre dois aeroportos é uma aresta. Se o voo de ida não garante o de volta, o grafo é direcionado (digrafo). O preço da passagem ou o tempo de voo é o peso da aresta (grafo ponderado). Se você quer saber se é possível voar de São Paulo a Tóquio (conectividade), ou qual a rota com menos escalas (BFS), ou a rota mais barata (Dijkstra), você está resolvendo problemas clássicos de grafos usando essa malha aérea como modelo.
Representação de Grafos: Matriz vs Lista de Adjacência
A escolha de como representar um grafo em Java dita a eficiência de espaço e tempo do seu sistema. Existem duas abordagens principais: 1. Matriz de Adjacência: Um array bidimensional boolean[][] ou int[][] de tamanho V x V. Excelente para grafos densos (onde o número de arestas E aproxima-se de V²). Verificar se existe uma aresta u -> v é O(1). No entanto, consome O(V²) de memória, o que é proibitivo para grafos esparsos. 2. Lista de Adjacência: Um array ou List de listas, como List<List<Edge>> ou Map<Integer, List<Edge>>. Cada vértice guarda apenas seus vizinhos diretos. Consome O(V + E) de memória, sendo ideal para grafos esparsos (a maioria dos cenários reais). Checar se existe aresta u -> v requer percorrer a lista de u, sendo O(grau(u)).
// Lista de Adjacência típica em Java para grafos ponderados
public class Graph {
private final int numVertices;
private final List<List<Edge>> adjList;
public Graph(int numVertices) {
this.numVertices = numVertices;
this.adjList = new ArrayList<>(numVertices);
for (int i = 0; i < numVertices; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int source, int target, int weight) {
adjList.get(source).add(new Edge(target, weight));
}
}
class Edge {
int target;
int weight;
public Edge(int target, int weight) {
this.target = target;
this.weight = weight;
}
}DFS vs BFS: O Explorador de Cavernas vs O Vazamento de Água
Imagine que você está investigando um labirinto. A Busca em Profundidade (DFS) é o explorador solitário que entra em um túnel e caminha até o fim (beco sem saída). Ao bater na parede, ele volta (backtrack) até a última bifurcação e tenta outro caminho. Ele usa uma pilha (stack) mental. Já a Busca em Largura (BFS) é como água vazando no labirinto: ela se espalha uniformemente por todos os túneis adjacentes ao mesmo tempo, nível por nível, cobrindo todos os caminhos de distância 1, depois distância 2, e assim por diante. Ela usa uma fila (queue) física de expansão.
Travessias de Grafo e Ordenação Topológica
DFS e BFS percorrem todos os vértices de um grafo em O(V + E): • DFS: Usa recursão (pilha de execução) ou uma Stack explícita. É ideal para detecção de ciclos em grafos direcionados (rastreando os nós atualmente na pilha de recursão), busca de componentes fortemente conexos e caminhos onde queremos ir o mais longe possível primeiro. • BFS: Usa uma Queue (Fila) iterativa. É a ferramenta certa para encontrar o caminho mais curto (mínimo de arestas) em grafos não ponderados (como conexões de 1º, 2º e 3º grau no LinkedIn). • Ordenação Topológica: Uma ordenação linear dos vértices de um Grafo Acíclico Direcionado (DAG) onde, para cada aresta direcionada u -> v, u vem antes de v. Essencial para compilação de módulos, execução de tarefas paralelas e resolução de dependências de beans (como o Spring Boot faz). O Algoritmo de Kahn (baseado em BFS) usa os graus de entrada (in-degrees) dos nós para remover progressivamente aqueles que não dependem de ninguém.
// Algoritmo de Kahn (Topological Sort via BFS)
// 1. Calcula in-degree (grau de entrada) de todos os nós
// 2. Coloca nós com in-degree 0 na fila
// 3. Enquanto a fila não estiver vazia:
// a. Remove nó u, adiciona na ordem topológica
// b. Decrementa o in-degree de todos os vizinhos de u
// c. Se o in-degree de algum vizinho v virar 0, adiciona na fila
// 4. Se a ordem gerada tiver tamanho < V, o grafo contém ciclos!Travessias e Kahn's Algorithm em Java
Abaixo está uma implementação limpa e eficiente em Java da detecção de ciclos usando DFS e da ordenação topológica usando o algoritmo de Kahn (BFS).
public class GraphAlgorithms {
// Detecção de ciclo em Grafo Direcionado usando DFS (cores/recursion stack)
public boolean hasCycle(int numVertices, List<List<Integer>> adj) {
boolean[] visited = new boolean[numVertices];
boolean[] recStack = new boolean[numVertices];
for (int i = 0; i < numVertices; i++) {
if (dfsCycleDetect(i, adj, visited, recStack)) return true;
}
return false;
}
private boolean dfsCycleDetect(int u, List<List<Integer>> adj, boolean[] visited, boolean[] recStack) {
if (recStack[u]) return true;
if (visited[u]) return false;
visited[u] = true;
recStack[u] = true;
for (int v : adj.get(u)) {
if (dfsCycleDetect(v, adj, visited, recStack)) return true;
}
recStack[u] = false; // Backtracking
return false;
}
// Algoritmo de Kahn para Ordenação Topológica (retorna null se houver ciclo)
public List<Integer> topologicalSort(int numVertices, List<List<Integer>> adj) {
int[] inDegree = new int[numVertices];
for (int u = 0; u < numVertices; u++) {
for (int v : adj.get(u)) {
inDegree[v]++;
}
}
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < numVertices; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int u = queue.poll();
order.add(u);
for (int v : adj.get(u)) {
inDegree[v]--;
if (inDegree[v] == 0) {
queue.offer(v);
}
}
}
return order.size() == numVertices ? order : null;
}
}Caminhos Mínimos: O GPS com Trânsito
Imagine planejar uma rota de carro de São Paulo ao Rio de Janeiro. Algumas estradas têm pedágios caros ou trânsito lento (pesos altos), outras são vias rápidas livre de custos (pesos baixos). Dijkstra é o seu aplicativo Waze clássico: ele calcula a rota mais rápida abrindo caminhos a partir do seu ponto inicial, focando sempre na menor distância acumulada até o momento. Mas e se houvesse estradas especiais que pagassem dinheiro para você passar (pesos negativos)? O Waze comum travaria e entraria em loop infinito. É aí que você precisaria de algoritmos mais robustos como o Bellman-Ford para evitar cair em buracos negros financeiros (ciclos de custo negativo).
Dijkstra, Bellman-Ford e Floyd-Warshall
O problema de caminho mínimo é resolvido por estratégias distintas baseadas no tipo de grafo e pesos de arestas: • Dijkstra: Algoritmo guloso (greedy) de fonte única. Usa uma fila de prioridades (PriorityQueue) para extrair o nó mais próximo não visitado. Funciona em O((V + E) log V). Restrição: NÃO aceita pesos negativos, pois assume que caminhos já processados não podem ser reduzidos (premissa de monotonicidade). • Bellman-Ford: Programação dinâmica de fonte única. Relaxa todas as E arestas do grafo repetidamente V-1 vezes. Roda em O(V * E). Vantagem: Suporta pesos negativos e detecta ciclos negativos (se uma aresta puder ser relaxada na V-ésima iteração, existe um ciclo de peso negativo). • Floyd-Warshall: Algoritmo para caminhos mínimos entre todos os pares (all-pairs). Usa programação dinâmica triplamente aninhada sobre a matriz de adjacência. Roda em O(V³). Ideal para grafos pequenos (V < 300) onde precisamos da resposta de qualquer nó para qualquer outro nó.
Algoritmo de Dijkstra em Java
Uma implementação robusta de Dijkstra em Java deve usar uma PriorityQueue para obter performance O((V+E) log V). Em Java, passamos uma instância de Comparator para a fila ordenar pelo custo acumulado.
public class DijkstraAlgorithm {
public static class Node {
int vertex;
int distance;
public Node(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
}
public int[] dijkstra(int start, int numVertices, List<List<Edge>> adj) {
int[] dist = new int[numVertices];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.distance, b.distance));
pq.offer(new Node(start, 0));
boolean[] visited = new boolean[numVertices];
while (!pq.isEmpty()) {
Node current = pq.poll();
int u = current.vertex;
if (visited[u]) continue; // Ignora duplicatas na fila
visited[u] = true;
for (Edge edge : adj.get(u)) {
int v = edge.target;
int weight = edge.weight;
if (!visited[v] && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.offer(new Node(v, dist[v]));
}
}
}
return dist;
}
}Árvores Geradoras Mínimas (MST): Prim e Kruskal
Uma Árvore Geradora Mínima (MST) é um subconjunto de arestas de um grafo conexo, não direcionado e ponderado, que conecta todos os vértices sem ciclos e com o menor peso total possível. Dois algoritmos gulosos clássicos resolvem isso em O(E log V): • Prim: Começa com um único nó e cresce a árvore adicionando, a cada passo, a aresta de menor peso que conecta um nó visitado a um não visitado (usa PriorityQueue). Indicado para grafos densos. • Kruskal: Ordena todas as arestas do grafo por peso e as adiciona na árvore uma a uma, desde que não criem ciclos. Excelente para grafos esparsos. Para verificar ciclos de forma hiper-eficiente, o Kruskal usa a estrutura de dados Union-Find (Conjuntos Disjuntos). • Union-Find: Mantém o controle de partições disjuntas de vértices. Possui duas operações principais: - find(i): Encontra o representante/raiz do conjunto ao qual o elemento i pertence. Otimizado com Path Compression (faz nós do caminho apontarem direto para a raiz durante a busca). - union(i, j): Une os conjuntos de i e j. Otimizado com Union by Rank (anexa a árvore menor sob a raiz da maior para evitar que a árvore fique desbalanceada).
Union-Find (Disjoint Set) e Kruskal em Java
Veja como implementar o Union-Find com Path Compression e Union by Rank, e como usá-lo para rodar o algoritmo de Kruskal para obter a MST em Java.
public class KruskalMST {
public static class Edge implements Comparable<Edge> {
int src, dest, weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
}
public static class DisjointSet {
private final int[] parent;
private final int[] rank;
public DisjointSet(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) parent[i] = i;
}
public int find(int i) {
if (parent[i] == i) return i;
return parent[i] = find(parent[i]); // Path Compression
}
public boolean union(int i, int j) {
int rootI = find(i);
int rootJ = find(j);
if (rootI == rootJ) return false; // Já estão no mesmo conjunto (ciclo detectado)
// Union by Rank
if (rank[rootI] < rank[rootJ]) {
parent[rootI] = rootJ;
} else if (rank[rootI] > rank[rootJ]) {
parent[rootJ] = rootI;
} else {
parent[rootJ] = rootI;
rank[rootI]++;
}
return true;
}
}
public List<Edge> kruskal(int numVertices, List<Edge> edges) {
Collections.sort(edges); // O(E log E)
DisjointSet ds = new DisjointSet(numVertices);
List<Edge> mst = new ArrayList<>();
for (Edge edge : edges) {
if (ds.union(edge.src, edge.dest)) {
mst.add(edge);
if (mst.size() == numVertices - 1) break;
}
}
return mst;
}
}