Algoritmos de Grafos

Implementando e visualizando BFS, DFS e Dijkstra

Introdução

Grafos são estruturas de dados fundamentais em ciência da computação, com aplicações em redes sociais, sistemas de navegação, otimização de rotas, e muito mais. Neste post, vamos implementar e visualizar três algoritmos clássicos de grafos.

Representação de Grafos

Primeiro, vamos criar uma classe para representar grafos:

from collections import defaultdict, deque
import heapq

class Grafo:
    def __init__(self, direcionado=False):
        self.grafo = defaultdict(list)
        self.direcionado = direcionado
        self.pesos = {}
    
    def adicionar_aresta(self, u, v, peso=1):
        """Adiciona uma aresta entre os vértices u e v"""
        self.grafo[u].append(v)
        self.pesos[(u, v)] = peso
        
        if not self.direcionado:
            self.grafo[v].append(u)
            self.pesos[(v, u)] = peso
    
    def vertices(self):
        """Retorna todos os vértices do grafo"""
        vertices = set()
        for u in self.grafo:
            vertices.add(u)
            for v in self.grafo[u]:
                vertices.add(v)
        return vertices
    
    def __str__(self):
        resultado = []
        for vertice in sorted(self.grafo.keys()):
            vizinhos = ', '.join(str(v) for v in self.grafo[vertice])
            resultado.append(f"{vertice} -> [{vizinhos}]")
        return '\n'.join(resultado)

# Criar grafo de exemplo
g = Grafo()
g.adicionar_aresta('A', 'B', 4)
g.adicionar_aresta('A', 'C', 2)
g.adicionar_aresta('B', 'C', 1)
g.adicionar_aresta('B', 'D', 5)
g.adicionar_aresta('C', 'D', 8)
g.adicionar_aresta('C', 'E', 10)
g.adicionar_aresta('D', 'E', 2)

print("Grafo criado:")
print(g)

Grafo criado:
A -> [B, C]
B -> [A, C, D]
C -> [A, B, D, E]
D -> [B, C, E]
E -> [C, D]

1. Busca em Largura (BFS)

A BFS explora o grafo nível por nível, visitando todos os vizinhos antes de avançar.

def bfs(grafo, inicio):
    """
    Busca em Largura (Breadth-First Search)
    Retorna a ordem de visitação e as distâncias
    """
    visitados = set()
    fila = deque([(inicio, 0)])  # (vértice, distância)
    ordem = []
    distancias = {inicio: 0}
    
    while fila:
        vertice, dist = fila.popleft()
        
        if vertice in visitados:
            continue
        
        visitados.add(vertice)
        ordem.append(vertice)
        
        for vizinho in grafo.grafo[vertice]:
            if vizinho not in visitados:
                fila.append((vizinho, dist + 1))
                if vizinho not in distancias:
                    distancias[vizinho] = dist + 1
    
    return ordem, distancias

# Executar BFS
ordem_bfs, dist_bfs = bfs(g, 'A')
print(f"\nOrdem de visitação (BFS): {' -> '.join(ordem_bfs)}")
print(f"Distâncias a partir de A: {dist_bfs}")

Ordem de visitação (BFS): A -> B -> C -> D -> E
Distâncias a partir de A: {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2}

2. Busca em Profundidade (DFS)

A DFS explora o grafo indo o mais fundo possível antes de retroceder.

def dfs(grafo, inicio):
    """
    Busca em Profundidade (Depth-First Search)
    Retorna a ordem de visitação
    """
    visitados = set()
    ordem = []
    
    def dfs_recursivo(vertice):
        visitados.add(vertice)
        ordem.append(vertice)
        
        for vizinho in grafo.grafo[vertice]:
            if vizinho not in visitados:
                dfs_recursivo(vizinho)
    
    dfs_recursivo(inicio)
    return ordem

# Executar DFS
ordem_dfs = dfs(g, 'A')
print(f"\nOrdem de visitação (DFS): {' -> '.join(ordem_dfs)}")

Ordem de visitação (DFS): A -> B -> C -> D -> E

3. Algoritmo de Dijkstra

Dijkstra encontra o caminho mais curto de um vértice para todos os outros.

def dijkstra(grafo, inicio):
    """
    Algoritmo de Dijkstra para caminho mais curto
    Retorna distâncias e caminhos
    """
    distancias = {v: float('inf') for v in grafo.vertices()}
    distancias[inicio] = 0
    anteriores = {v: None for v in grafo.vertices()}
    
    # Fila de prioridade: (distância, vértice)
    pq = [(0, inicio)]
    visitados = set()
    
    while pq:
        dist_atual, vertice_atual = heapq.heappop(pq)
        
        if vertice_atual in visitados:
            continue
        
        visitados.add(vertice_atual)
        
        for vizinho in grafo.grafo[vertice_atual]:
            peso = grafo.pesos.get((vertice_atual, vizinho), 1)
            distancia = dist_atual + peso
            
            if distancia < distancias[vizinho]:
                distancias[vizinho] = distancia
                anteriores[vizinho] = vertice_atual
                heapq.heappush(pq, (distancia, vizinho))
    
    return distancias, anteriores

def reconstruir_caminho(anteriores, inicio, fim):
    """Reconstrói o caminho do início ao fim"""
    caminho = []
    atual = fim
    
    while atual is not None:
        caminho.append(atual)
        atual = anteriores[atual]
    
    return caminho[::-1] if caminho[0] == inicio else []

# Executar Dijkstra
dist_dijkstra, anteriores = dijkstra(g, 'A')

print("\nAlgoritmo de Dijkstra a partir de A:")
print("Distâncias mais curtas:")
for vertice in sorted(dist_dijkstra.keys()):
    caminho = reconstruir_caminho(anteriores, 'A', vertice)
    print(f"  A -> {vertice}: {dist_dijkstra[vertice]} (caminho: {' -> '.join(caminho)})")

Algoritmo de Dijkstra a partir de A:
Distâncias mais curtas:
  A -> A: 0 (caminho: A)
  A -> B: 3 (caminho: )
  A -> C: 2 (caminho: )
  A -> D: 8 (caminho: )
  A -> E: 10 (caminho: )

Visualização com Mermaid

Podemos visualizar o grafo usando diagramas Mermaid:

graph LR
    A[A] -->|4| B[B]
    A -->|2| C[C]
    B -->|1| C
    B -->|5| D[D]
    C -->|8| D
    C -->|10| E[E]
    D -->|2| E
    
    style A fill:#e1f5ff
    style E fill:#ffe1e1

Comparação dos Algoritmos

Algoritmo	Complexidade	Uso Principal	Garante Caminho Mínimo?
BFS	O(V + E)	Caminho mais curto (não ponderado)	Sim (grafos não ponderados)
DFS	O(V + E)	Exploração, detecção de ciclos	Não
Dijkstra	O((V + E) log V)	Caminho mais curto (ponderado)	Sim (pesos não negativos)

Onde: - V = número de vértices - E = número de arestas

Aplicações Práticas

BFS

• Encontrar o menor número de conexões em redes sociais
• Resolver quebra-cabeças (ex: cubo mágico)
• Broadcast em redes

DFS

• Detecção de ciclos
• Ordenação topológica
• Resolver labirintos

Dijkstra

• GPS e sistemas de navegação
• Roteamento de redes
• Planejamento de rotas de entrega

Visualização do Caminho Mais Curto

Vamos visualizar o caminho mais curto de A para E:

graph LR
    A[A] -.->|4| B[B]
    A ==>|2| C[C]
    B -.->|1| C
    B -.->|5| D[D]
    C -.->|8| D
    C -.->|10| E[E]
    D ==>|2| E[E]
    
    style A fill:#90EE90
    style C fill:#FFD700
    style D fill:#FFD700
    style E fill:#FF6B6B
    
    classDef pathNode fill:#FFD700,stroke:#333,stroke-width:3px
    class C,D pathNode

O caminho mais curto de A para E é: A → C → D → E com custo total de 6.

Conclusão

Algoritmos de grafos são ferramentas poderosas para resolver problemas complexos. A escolha do algoritmo depende:

• Estrutura do grafo (direcionado/não direcionado, ponderado/não ponderado)
• Objetivo (exploração completa vs. caminho mais curto)
• Restrições (tempo, memória)

Exercício

Tente implementar: 1. Algoritmo de Bellman-Ford (permite pesos negativos) 2. Algoritmo A* (heurística para busca mais eficiente) 3. Detecção de ciclos usando DFS

---

Código completo disponível no GitHub