Introdução à Teoria dos Grafos

1. O Mundo Conectado

Um Grafo \(G(V, E)\) é uma estrutura matemática composta por: - \(V\): Um conjunto de Vértices (ou nós). - \(E\): Um conjunto de Arestas (ou arcos) que conectam pares de vértices.

Grafos modelam relacionamentos: - Redes Sociais: Vértices = Pessoas, Arestas = Amizades. - Mapas: Vértices = Cidades, Arestas = Estradas. - Web: Vértices = Páginas, Arestas = Hyperlinks.

Terminologia Essencial

  • Grau (Degree): Número de arestas conectadas a um vértice.
  • Grafo Direcionado (Digrafo): Arestas têm sentido (\(A \rightarrow B\)). Ex: Twitter (Seguir).
  • Grafo Não-Direcionado: O sentido é bidirecional (\(A - B\)). Ex: Facebook (Amizade).
  • Ponderado (Weighted): Arestas têm um “peso” ou custo. Ex: Distância em km.
  • Caminho (Path): Sequência de vértices conectados por arestas.
  • Ciclo: Caminho que começa e termina no mesmo vértice.

2. Como representar no computador?

A escolha da representação afeta drasticamente a complexidade de tempo e memória. Seja \(V\) o número de vértices e \(E\) o número de arestas.

2.1. Matriz de Adjacência

Uma matriz \(M\) de tamanho \(V \times V\), onde: - \(M[i][j] = 1\) (ou peso) se existe aresta de \(i\) para \(j\). - \(M[i][j] = 0\) (ou \(\infty\)) se não existe.

Vantagens Desvantagens
Verificar se \(u\) conecta com \(v\) em \(O(1)\). Gasta muita memória \(O(V^2)\).
Simples de implementar. Iterar sobre vizinhos é lento \(O(V)\).

Uso: Apenas para grafos pequenos (\(V \le 2000\)) ou muito densos (\(E \approx V^2\)).

2.2. Lista de Adjacência (Padrão Ouro)

Um vetor de listas. Para cada vértice \(u\), armazenamos uma lista com seus vizinhos.

Vantagens Desvantagens
Memória eficiente \(O(V + E)\). Verificar aresta \((u,v)\) é \(O(Grau(u))\).
Iterar vizinhos é rápido \(O(Grau(u))\). Leve overhead de ponteiros.

Uso: Padrão para 99% dos problemas de competições e vida real (grafos esparsos).

3. Implementação em Java

Em C++, usamos vector<int> adj[]. Em Java, temos um pequeno problema: arrays de genéricos (ArrayList<Integer>[]) causam warnings. Soluções comuns: 1. ArrayList<ArrayList<Integer>> (Mais OO, levemente mais lento e verboso). 2. List<Integer>[] com casting (Mais compacto).

Modelo Padrão (Adjacency List)

import java.util.*;

public class Grafo {
    // Vértices rotulados de 0 a V-1
    private int V;
    private List<List<Integer>> adj;

    public Grafo(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        
        // Inicializa as listas vazias
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    // Adiciona aresta não-direcionada
    public void addEdge(int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u); // Remova esta linha se for Direcionado
    }

    // Exibe o grafo
    public void printGraph() {
        for (int i = 0; i < V; i++) {
            System.out.print("Vértice " + i + ":");
            for (Integer vizinho : adj.get(i)) {
                System.out.print(" -> " + vizinho);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Grafo g = new Grafo(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        
        g.printGraph();
    }
}

Grafo Ponderado (Com Pesos)

Se o grafo tem pesos, a lista de adjacência precisa armazenar pares (vizinho, peso). Em Java, criamos uma classe Edge.

class Aresta {
    int destino;
    int peso;
    
    public Aresta(int d, int p) {
        this.destino = d;
        this.peso = p;
    }
}

// Na classe Grafo:
private List<List<Aresta>> adj;

4. Edge List (Lista de Arestas)

Às vezes (ex: Kruskal para MST, Bellman-Ford), não precisamos saber quem são os vizinhos de \(u\). Só precisamos da lista de todas as arestas.

class Edge implements Comparable<Edge> {
    int u, v, weight;
    // construtor...
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

List<Edge> arestas = new ArrayList<>();

Isso simplifica a ordenação de arestas por peso.

5. Dicas de Entrada (Input)

Em problemas de juiz online, a entrada geralmente é dada assim:

5 6  (5 vértices, 6 arestas)
0 1
0 2
1 3
...

Template de Leitura:

Scanner sc = new Scanner(System.in);
int V = sc.nextInt();
int E = sc.nextInt();

// Inicializa List<List<Integer>>...

for(int i=0; i<E; i++) {
    int u = sc.nextInt(); // Se vértices forem 1-based, use (u-1)
    int v = sc.nextInt();
    addToGraph(u, v);
}

Atenção: Se os vértices forem rotulados de 1 a N, lembre-se de subtrair 1 para usar índices 0 a N-1 nos Lists.

Back to top