Pós-graduação → Personalização → Otimização Combinatória ↓
Algoritmos de grafos
Grafos são estruturas matemáticas usadas para modelar relacionamentos emparelhados entre objetos. Um grafo neste contexto é composto por vértices (também chamados de nós ou pontos) que são conectados por arestas (também chamadas de links ou linhas). Algoritmos de grafos são procedimentos matemáticos projetados para resolver problemas envolvendo grafos.
Importância dos algoritmos de grafos
Grafos são fundamentalmente importantes em muitos campos, incluindo ciência da computação, biologia e ciências sociais. Eles ajudam a resolver problemas como fluxo de rede, encontrar caminhos mais curtos, criar árvores de abrangência, e muito mais. Vamos explorar alguns algoritmos básicos e avançados de grafos.
Definições básicas
Antes de entrar nos algoritmos, é essencial entender alguns termos básicos relacionados a grafos.
- Vértice (ou nó): O ponto em um grafo onde as arestas se encontram.
- Aresta (ou link): Uma conexão entre dois vértices.
- Adjacência: Dois vértices são adjacentes se estiverem diretamente conectados por uma aresta.
- Caminho: Uma sequência de arestas que conecta uma sequência de vértices.
- Ciclo: Um caminho que começa e termina no mesmo vértice.
- Grafo conectado: Um grafo no qual existe um caminho entre cada par de vértices.
Tipos de grafos
- Grafo dirigido (digrafo): Um grafo no qual as arestas têm direções. Cada aresta é um par ordenado de vértices.
- Grafo não dirigido: Um grafo no qual as arestas não têm direção. Cada aresta é um par não ordenado de vértices.
- Grafo ponderado: Um grafo em que cada aresta tem um valor numérico (peso) associado a ela.
- Grafo não ponderado: Um grafo no qual as arestas não têm pesos.
- Grafo completo: Um grafo no qual existe exatamente uma aresta entre cada par de vértices.
Representação de grafos
Grafos podem ser representados de duas maneiras principais:
Matriz de adjacência
A matriz de adjacência é uma matriz 2D onde cada elemento indica se há uma aresta entre pares de vértices.
a = [
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 1],
[0, 1, 1, 0]
]
Esta matriz mostra um grafo com 4 vértices e arestas entre os pares (0,1), (1,2), (1,3) e (2,3).
Lista de adjacência
A lista de adjacência representa o grafo como uma lista de vértices, onde cada vértice tem sua própria lista de vértices adjacentes.
{
0: [1],
1: [0, 2, 3],
2: [1, 3],
3: [1, 2]
}
Nesta lista, o vértice 0 está conectado ao vértice 1, o vértice 1 está conectado aos vértices 0, 2 e 3, e assim por diante.
Algoritmos de busca em grafos
Busca em grafos significa o processo de visitar cada vértice de um grafo. Existem duas maneiras principais de atravessar um grafo:
Busca em Largura (BFS)
BFS é um método que itera através de um grafo explorando os nós vizinhos localizados na profundidade atual antes de passar para os nós localizados no próximo nível de profundidade.
def bfs(graph, inicio):
visitado = set()
fila = [inicio]
while fila:
vertice = fila.pop(0)
if vertice not in visitado:
visitado.add(vertice)
fila.extend(set(graph[vertice]) - visitado)
return visitado
No código acima, um grafo é percorrido começando do vértice inicio. O método BFS usa uma fila para acompanhar os pontos de vértice a serem visitados a seguir.
Exemplo de BFS em ação
O SVG acima mostra um grafo simples com vértices numerados de 0 a 3. Começando do vértice 0, BFS visitará os nós nesta ordem: 0, 1, 3, 2.
Busca em Profundidade (DFS)
DFS é um método de atravessamento em que a profundidade é priorizada e se avança o máximo possível ao longo de um ramo antes de retroceder.
def dfs(graph, inicio, visitado=None):
if visitado is None:
visitado = set()
visitado.add(inicio)
for proximo in graph[inicio]:
if proximo not in visitado:
dfs(graph, proximo, visitado)
return visitado
No código DFS, o método é chamado recursivamente e a pilha é usada através das chamadas de função para manter o caminho.
Exemplo de DFS em ação
Para o mesmo grafo, DFS visitará os nós nesta ordem: 0, 1, 2, 3.
Algoritmo de caminho mais curto
O objetivo dos algoritmos de grafos é frequentemente encontrar o caminho mais curto entre os nós. Aqui estão dois algoritmos bem conhecidos para achar o caminho mais curto:
Algoritmo de Dijkstra
O algoritmo de Dijkstra encontra o caminho mais curto do vértice inicial para todos os outros vértices em um grafo ponderado.
import heapq
def dijkstra(graph, inicio):
fila = []
heapq.heappush(fila, (0, inicio))
distancias = {nó: float('infinite') for nó in graph}
distancias[inicio] = 0
while fila:
distancia_atual, nó_atual = heapq.heappop(fila)
if distancia_atual > distancias[nó_atual]:
continue
for vizinho, peso in graph[nó_atual].items():
distancia = distancia_atual + peso
if distancia < distancias[vizinho]:
distancias[vizinho] = distancia
heapq.heappush(fila, (distancia, vizinho))
return distancias
Este algoritmo mantém uma fila para encontrar as arestas com o menor peso acumulado primeiro. Ele usa uma fila de prioridade (min-heap) para obter eficientemente a aresta com a menor distância.
Algoritmo de Bellman-Ford
O algoritmo de Bellman-Ford calcula os caminhos mais curtos de um único vértice de origem para todos os outros vértices em um grafo. Ele pode lidar com grafos com pesos negativos.
def bellman_ford(graph, inicio):
distancia = {i: float('inf') for i in graph}
distancia[inicio] = 0
for _ in range(len(graph) - 1):
for vertice in graph:
for vizinho, peso in graph[vertice].items():
if distancia[vertice] + peso < distancia[vizinho]:
distancia[vizinho] = distancia[vertice] + peso
for vertice in graph:
for vizinho, peso in graph[vertice].items():
if distancia[vertice] + peso < distancia[vizinho]:
raise ValueError("O grafo contém um ciclo de peso negativo")
return distancia
Diferente do algoritmo de Dijkstra, Bellman-Ford funciona bem com grafos contendo arestas com pesos negativos. Ele verifica repetidamente cada aresta para garantir que os caminhos ótimos foram encontrados.
Algoritmo de árvore geradora mínima (MST)
A árvore geradora mínima de um grafo conectado e não dirigido é um subconjunto de arestas que conecta todos os vértices sem quaisquer ciclos e com o menor peso de aresta total possível.
Algoritmo de Kruskal
O algoritmo de Kruskal constrói a MST adicionando arestas uma por uma, começando pela menor, e adicionando apenas aquelas arestas que não formam ciclos.
def kruskal(graph):
pai = {}
def encontrar(n):
while pai[n] != n:
n = pai[n]
return n
def uniao(n1, n2):
raiz1 = encontrar(n1)
raiz2 = encontrar(n2)
pai[raiz2] = raiz1
graph.sort(key=lambda x: x[2])
for n1, n2, _ in graph:
pai[n1] = n1
pai[n2] = n2
mst = []
for n1, n2, peso in graph:
if encontrar(n1) != encontrar(n2):
uniao(n1, n2)
mst.append((n1, n2, peso))
return mst
Este algoritmo começa classificando todas as arestas por peso. Ele usa uma estrutura de dados de união-busca para manter o controle dos componentes conectados e garantir que não sejam formados ciclos.
Algoritmo de Prim
O algoritmo de Prim constrói uma MST começando de um vértice arbitrário e adicionando sucessivamente a aresta de menor peso dos vértices já selecionados para os vértices ainda não selecionados.
import heapq
def prim(graph, inicio):
mst = []
visitado = set()
min_arestas = [(0, inicio, None)]
while min_arestas:
peso, vertice, de = heapq.heappop(min_arestas)
if vertice in visitado:
continue
visitado.add(vertice)
if de is not None:
mst.append((de, vertice, peso))
for proximo_vertice, proximo_peso in graph[vertice].items():
if proximo_vertice not in visitado:
heapq.heappush(min_arestas, (proximo_peso, proximo_vertice, vertice))
return mst
O algoritmo de Prim usa uma fila de prioridade para expandir sempre o nó na borda atual com o menor custo.
Conclusão
Algoritmos de grafos oferecem soluções para uma ampla gama de problemas relacionados a redes de nós e arestas. Seja encontrando o caminho mais curto, conexões ótimas ou atravessando nós, esses algoritmos desempenham um papel vital na solução eficiente de problemas complexos. Compreender as definições básicas, representações e principais algoritmos como BFS, DFS, Dijkstra, Bellman-Ford, Kruskal e Prim é crucial para alavancar algoritmos de grafos em aplicações da vida real.
Comentários