Grafos
Introdução a Grafos
Um grafo é uma estrutura de dados não linear composta por vértices (nós) e arestas (arcos), que representam conexões entre eles. Grafos são usados para modelar relações em problemas como redes, rotas e conectividade.
Componentes Básicos
- Vértice (V): Unidade fundamental (ex: cidades em um mapa).
- Aresta (E): Conexão entre vértices (ex: estradas).
- Grau de um vértice: Número de arestas conectadas a ele.
Classificação de Grafos
- Direcionado (digrafo): Arestas têm direção (ex: A → B ≠ B → A).
- Não-direcionado: Arestas bidirecionais (ex: A-B ≡ B-A).
- Ponderado: Arestas com pesos (ex: distâncias).
- Cíclico/Acíclico: Presença ou ausência de ciclos.
Representações
- Matriz de adjacência: Matriz quadrada onde células indicam conexões.
- Lista de adjacência: Lista encadeada armazenando vizinhos de cada vértice.
Algoritmos Importantes
- Busca em Largura (BFS): Explora por níveis, usa fila.
- Busca em Profundidade (DFS): Explora ramificações, usa pilha/recursão.
- Dijkstra: Menor caminho em grafos ponderados (pesos não negativos).
- Prim/Kruskal: Árvore geradora mínima (conecta todos os vértices com menor custo).
Aplicações em Concursos
Questões frequentes envolvem:
- Identificação de componentes conexos.
- Cálculo de menor caminho (ex: redes de transporte).
- Detecção de ciclos ou ordenação topológica (ex: tarefas dependentes).