⚙️ Algoritmos em Grafos 🔗📊

Os algoritmos em grafos são ferramentas poderosas para analisar, buscar e otimizar conexões em redes complexas. Eles são aplicados em roteadores de internet, GPS, redes sociais, engenharia, inteligência artificial e muito mais.

---

🔍 1. Busca em Largura (BFS – Breadth-First Search)

👉 O que faz?

Explora o grafo por camadas, indo primeiro nos vértices mais próximos de um ponto inicial.

✅ Aplicações:

• Verificar conectividade

• Encontrar o caminho mais curto (em grafos não ponderados)

• Resolver labirintos

🧠 Como funciona?

1. Coloca o vértice inicial em uma fila.

2. Marca como visitado.

3. Visita todos os vizinhos antes de ir para os vizinhos dos vizinhos.

---

🔎 2. Busca em Profundidade (DFS – Depth-First Search)

👉 O que faz?

Explora o grafo profundamente em uma direção antes de voltar e explorar outros caminhos.

✅ Aplicações:

• Detectar ciclos

• Verificar componentes conexas

• Ordenação topológica em grafos direcionados acíclicos

🧠 Como funciona?

1. Começa em um vértice inicial.

2. Vai o mais fundo possível.

3. Retrocede quando não há mais vizinhos a visitar.

---

🧭 3. Dijkstra – Caminho Mínimo

👉 O que faz?

Calcula o caminho mais curto de um vértice para os demais em grafos com pesos positivos.

✅ Aplicações:

• GPS e roteamento

• Redes de logística e transporte

🧠 Como funciona?

1. Inicializa a distância de todos os vértices como ∞, exceto o inicial (0).

2. Atualiza as distâncias conforme visita os vértices vizinhos.

3. Usa uma fila de prioridade (heap).

---

🌉 4. Kruskal – Árvore Geradora Mínima (MST)

👉 O que faz?

Encontra o subconjunto de arestas com menor custo total que conecta todos os vértices sem ciclos.

✅ Aplicações:

• Conexão eficiente de redes (internet, estradas)

• Planejamento de infraestrutura

🧠 Como funciona?

1. Ordena todas as arestas por peso.

2. Adiciona as menores arestas ao conjunto, sem formar ciclos.

3. Usa a estrutura de conjuntos disjuntos (Union-Find).

---

🌲 5. Prim – Árvore Geradora Mínima

👉 Diferença para Kruskal?

Enquanto Kruskal escolhe arestas independentes, Prim cresce uma árvore a partir de um vértice.

✅ Aplicações:

• Similares às de Kruskal

• Melhor em grafos densos

---

🔄 6. Bellman-Ford – Caminhos Mínimos com Pesos Negativos

👉 O que faz?

Calcula caminhos mínimos em grafos com pesos negativos.

✅ Aplicações:

• Análise econômica e financeira

• Redes com penalidades ou descontos

---

⛓️ 7. Floyd-Warshall – Caminhos entre Todos os Pares

👉 O que faz?

Calcula o caminho mais curto entre todos os pares de vértices.

✅ Aplicações:

• Redes de tráfego

• Telecomunicações

• Análise de redes sociais

---

🧠 Tabela-Resumo dos Algoritmos

Algoritmo	Função Principal	Grafos com Pesos Negativos?	Complexidade
BFS	Busca por camadas	Não usa pesos	O(V + E)
DFS	Busca em profundidade	Não usa pesos	O(V + E)
Dijkstra	Caminho mínimo de um ponto	❌	O(V²) ou O(E log V) com heap
Bellman-Ford	Caminhos mínimos com pesos negativos	✅	O(VE)
Floyd-Warshall	Caminhos entre todos os pares	✅	O(V³)
Kruskal	Árvore geradora mínima	❌	O(E log E)
Prim	Árvore geradora mínima	❌	O(V²) ou O(E log V) com heap