| Matrícula | Nome |
|---|---|
| 21/1062240 | Mateus Bastos dos Santos |
| 21/1062320 | Miguel Arthur Oliveira de Lima |
Exercícios para o trabalho da disciplina de Estruturas de Dados e Algoritmos II (EDA2), com foco em estruturas baseadas em grafos e técnicas de busca.
O objetivo é compreender o funcionamento, a implementação e a aplicação prática de algoritmos fundamentais de grafos, utilizando exercícios da plataforma LeetCode para validação.
Foram selecionados 2 exercícios de nível Médio e 2 exercícios de nível Difícil, todos relacionados a grafos, conectividade, busca em largura (BFS), busca em profundidade (DFS) e teoria de redes.
| Exercício | Dificuldade | Estrutura Principal |
|---|---|---|
| 01. Number of Islands (200) | Médio | Grid Graph / DFS / BFS |
| 02. Word Ladder (127) | Difícil | BFS / Graph Construction |
| 03. Rotting Oranges (994) | Médio | BFS Multi-Fonte / Grid |
| 04. Critical Connections in a Network (1192) | Difícil | Graph / DFS / Tarjan (Bridges) |
Autor: Miguel Arthur
O objetivo é determinar quantas ilhas existem em uma matriz onde '1' representa terra e '0' representa água.
Uma ilha é formada por células conectadas verticalmente ou horizontalmente.
A solução utiliza busca em profundidade (DFS) ou busca em largura (BFS) para percorrer cada componente conectado.
- Exploração de vizinhos em grid
- DFS/BFS para marcar território visitado
- Contagem de componentes conectados
Autor: Miguel Arthur
O desafio consiste em transformar uma palavra inicial em uma palavra final, alterando apenas 1 letra por vez, desde que cada nova palavra pertença ao dicionário fornecido.
O objetivo é calcular o menor número de transformações possíveis.
A solução utiliza BFS, tratando palavras como vértices de um grafo implícito.
- Construção de grafo implícito baseado em padrões
- BFS para menor caminho em grafos não ponderados
- Otimização com hashing de padrões intermediários
Autor: Mateus Bastos
Cada laranja podre espalha a podridão para laranjas frescas adjacentes (4-direções) a cada minuto.
O problema exige determinar quanto tempo todas as laranjas levarão para apodrecer, ou retornar -1 se alguma ficar isolada.
A solução utiliza BFS com múltiplas fontes, iniciando a fila com todas as laranjas podres do grid.
- BFS multi-fonte
- Processamento em camadas (nível por minuto)
- Detecção de células inalcançáveis
Autor: Mateus Bastos
Dado um grafo não direcionado representando conexões de rede, o objetivo é encontrar arestas críticas (bridges).
Uma aresta é crítica se, ao removê-la, o grafo deixa de ser totalmente conectado.
A solução utiliza o algoritmo de Tarjan, baseado em DFS, que calcula tempos de descoberta e o menor "low-link" alcançável.
- Teoria de grafos: Bridges
- DFS + Tarjan (low-link values)
- Representação de grafo com lista de adjacência
- Acesse: https://leetcode.com
- Crie uma conta ou faça login.
- Pesquise pelo número (ex: “200” ou “1192”)
- Ou clique nos links fornecidos acima.
- Utilize C++ para todos os exercícios.
- Copie o código da sua solução local.
- Cole no editor do LeetCode.
- Clique em Run e depois Submit.
Explicamos todos os códigos implementados na plataforma LeetCode, descrevendo a lógica dos algoritmos de busca e teoria dos grafos aplicada em cada exercício.
Disciplina: Estruturas de Dados e Algoritmos II — Universidade de Brasília
Período: 2025.2