Grafo (Graph)

Definição

Um Grafo (Graph) é uma estrutura de dados que representa um conjunto de vértices (ou nós) conectados por arestas (ou ligações).

Os grafos podem ser direcionados (com sentido definido nas conexões) ou não direcionados (as ligações funcionam nos dois sentidos). Também podem ser ponderados, quando cada aresta possui um valor associado, como distância, tempo ou custo.

Por que usar

Grafos são essenciais para modelar relacionamentos complexos. Alguns exemplos comuns:

• Mapas de rotas e estradas;
• Redes sociais e conexões entre usuários;
• Relações entre entidades em bancos de dados;
• Resolução de dependências em compiladores ou pacotes;
• Busca de caminhos e algoritmos como Dijkstra, BFS, DFS.

Além disso, grafos são a base para muitos algoritmos clássicos da ciência da computação.

Exemplo prático (em Java)

Abaixo, um exemplo de grafo não direcionado em Java, implementado com lista de adjacência usando HashMap e ArrayList:

import java.util.*;

public class Grafo {
    // Mapa que armazena os vértices e suas conexões
    private Map<String, List<String>> adjacencias = new HashMap<>();

    // Adiciona um novo vértice
    public void adicionarVertice(String nome) {
        adjacencias.putIfAbsent(nome, new ArrayList<>());
    }

    // Adiciona uma aresta entre dois vértices
    public void adicionarAresta(String origem, String destino) {
        if (!adjacencias.containsKey(origem) || !adjacencias.containsKey(destino)) return;
        adjacencias.get(origem).add(destino);
        adjacencias.get(destino).add(origem); // remova se for grafo direcionado
    }

    // Exibe o grafo
    public void imprimirGrafo() {
        for (String vertice : adjacencias.keySet()) {
            System.out.println("Vértice " + vertice + " → " + adjacencias.get(vertice));
        }
    }

    // Exemplo de uso
    public static void main(String[] args) {
        Grafo grafo = new Grafo();
        grafo.adicionarVertice("A");
        grafo.adicionarVertice("B");
        grafo.adicionarVertice("C");
        grafo.adicionarVertice("D");

        grafo.adicionarAresta("A", "B");
        grafo.adicionarAresta("A", "C");
        grafo.adicionarAresta("B", "D");

        grafo.imprimirGrafo();
    }
}

Esse código cria um grafo não direcionado simples, onde cada vértice pode se conectar a vários outros. A estrutura pode ser facilmente adaptada para grafos direcionados ou ponderados.

Relacionados

• Árvore (Tree)
• Fila (Queue)
• Conjunto (Set)