Teoria dos Grafos e Algoritmos de Busca: Da Conectividade ao A* Heurístico

Teoria dos grafos e algoritmos de busca

Abra o aplicativo de mapas no seu celular ou olhe para o diagrama de linhas do metrô da sua cidade. Cada estação é um ponto desenhado no papel, e cada linha de trilho que conecta duas estações é uma reta ligando esses pontos. Você não precisa saber a coordenada física exata de cada curva sob o asfalto para saber que, se quiser ir da estação Central até o Aeroporto, precisará passar por três baldeações intermediárias. Essa abstração pura, onde o que importa são os pontos e as ligações entre eles, é a teoria dos grafos.

Se a teoria dos conjuntos define como agrupamos dados, a teoria dos grafos define como os dados conversam entre si. Redes sociais, árvores de dependência do gerenciador de pacotes de Go, o roteamento de pacotes TCP/IP na Internet e a inteligência artificial que move inimigos em jogos sem bater na parede são todos, sem exceção, problemas de grafos.

Esta aula ensina a matemática dos grafos e os algoritmos mais famosos criados pela ciência da computação. Começaremos com a anatomia do grafo e sua representação em memória em Go (seções 1 e 2), exploraremos as buscas fundamentais BFS e DFS (seções 3 e 4), subiremos o nível para os algoritmos de menor caminho ponderado com Dijkstra e A* (seções 5 e 6), passaremos pelo catálogo de outros algoritmos clássicos como Bellman-Ford e Kruskal (seção 7), e fecharemos com uma implementação completa e comentada do A* em Go, erros comuns, exercícios e glossário.

1. Anatomia de um grafo

Formalmente, um grafo G é definido como um par ordenado G = (V, E), onde:

• V é um conjunto não-vazio de vértices (também chamados de nós).
• E é um conjunto de arestas (arestas ou arcos), onde cada aresta conecta um par de vértices.

Os grafos são classificados de acordo com a natureza de suas conexões:

• Grafos não-direcionados: as arestas são vias de mão dupla. Se existe uma aresta entre A e B, o tráfego flui livremente nos dois sentidos (exemplo: conexões de amizade no LinkedIn).
• Grafos direcionados (Dígrafos): as arestas possuem sentido obrigatório, representadas por setas. A aresta (A, B) permite ir de A para B, mas não garante a volta (exemplo: seguidores no Twitter/X ou chamadas de dependência de funções).
• Grafos ponderados: cada aresta carrega um número associado, chamado de peso ou custo (exemplo: distância em quilômetros em uma rodovia, latência em milissegundos em um cabo submarino ou pedágio financeiro).
• Ciclos e DAGs: se um caminho parte de um nó e consegue retornar a ele mesmo, o grafo possui um ciclo. Um Grafo Acíclico Direcionado (DAG) é um dígrafo sem ciclos, a estrutura fundamental de pipelines de build, sistemas de controle de versão (Git) e agendadores de tarefas.

2. Como representar grafos na memória

No código de software, um grafo precisa ser guardado na memória RAM. Existem duas formas clássicas de fazer isso, cada uma com trade-offs severos de espaço e velocidade:

Matriz de adjacência

Uma matriz quadrada de tamanho |V| × |V|, onde a célula M[i][j] guarda 1 (ou o peso da aresta) se houver conexão do nó i para o nó j, e 0 caso contrário.

• Vantagem: consultar se dois nós são vizinhos (existeAresta(u, v)) é instantâneo em tempo O(1).
• Desvantagem: o consumo de memória é sempre quadrático O(|V|²). Se você tiver 100.000 usuários em uma rede social onde cada um tem em média 50 amigos, uma matriz alocará 10 bilhões de posições, das quais 99,99% serão zeros inúteis.

Lista de adjacência

Um mapa ou array onde cada vértice aponta para uma lista simples contendo apenas os seus vizinhos reais.

• Vantagem: consome memória estritamente proporcional ao tamanho real do grafo O(|V| + |E|), ideal para grafos esparsos (que representam 99% dos casos do mundo real).
• Desvantagem: verificar se dois nós específicos estão conectados exige percorrer a lista de vizinhos em tempo O(grau(u)).

O diagrama acima mostra as duas visões. Na parte superior, temos a representação matemática de um grafo direcionado e ponderado com nós de A a D. Na parte inferior, vemos a tradução exata disso para uma lista de adjacência em Go usando map[string][]Aresta: o nó A aponta diretamente para uma lista com C (peso 2) e B (peso 4), sem alocar espaço para conexões que não existem.

3. Busca em largura (BFS): o menor caminho sem pesos

Como explorar um grafo a partir de um nó de partida? O primeiro algoritmo fundamental é a Busca em Largura (Breadth-First Search ou BFS).

A intuição do BFS é como atirar uma pedra em um lago calmo: as ondas se espalham em círculos concêntricos a partir do ponto de impacto. O algoritmo visita primeiro todos os vizinhos diretos (distância 1), depois todos os vizinhos dos vizinhos (distância 2), e assim sucessivamente.

Para garantir essa ordem de expansão por camadas, o BFS utiliza obrigatoriamente uma fila FIFO (First-In, First-Out):

1. Enfileira o nó inicial e marca como visitado.
2. Enquanto a fila não estiver vazia, retira o primeiro nó.
3. Para cada vizinho não-visitado, marca como visitado e coloca no fim da fila.

A propriedade de ouro do BFS: em qualquer grafo não-ponderado (onde todas as arestas têm o mesmo custo unitário), o BFS tem a garantia matemática de encontrar o menor caminho entre a origem e qualquer outro nó acessível, com complexidade de tempo linear O(|V| + |E|).

4. Busca em profundidade (DFS): mergulho e backtracking

A Busca em Profundidade (Depth-First Search ou DFS) adota a estratégia oposta: ela se comporta como uma pessoa explorando um labirinto escuro. Ela escolhe um corredor e corre para frente o mais longe possível até atingir um beco sem saída; só então ela retrocede (backtracking) até a última bifurcação e tenta outro caminho.

O DFS utiliza uma pilha LIFO (Last-In, First-Out), implementada quase sempre de forma natural através de chamadas de funções recursivas que aproveitam a pilha de execução (call stack) da linguagem.

O diagrama resume o contraste entre os dois motores de busca. À esquerda, o BFS processa nós em ondas ordenadas por uma fila, garantindo caminhos mínimos sem pesos. À direita, o DFS mergulha em galhos verticais através de chamadas empilhadas.

Para que serve o DFS se ele não garante o menor caminho? O DFS é a ferramenta perfeita para compreender a topologia e a estrutura do grafo:

• Detecção de ciclos: se durante o mergulho você encontrar um nó que já está na pilha de chamada ativa atual, você detectou um ciclo fechado.
• Ordenação topológica: ordenando os nós pelo momento em que a recursão do DFS termina (pós-ordem reversa), obtemos uma sequência linear válida para compilar arquivos ou executar tarefas com dependências.
• Componentes conexos: identificar ilhas isoladas de servidores que perderam comunicação com o restante da rede.

5. O Algoritmo de Dijkstra: menor caminho ponderado

O BFS encontra o caminho com o menor número de saltos, mas no mundo real as arestas têm custos diferentes: viajar de carro por uma rodovia expressa de 50 km com asfalto perfeito pode ser mais rápido do que cortar caminho por uma estrada de terra esburacada de 30 km.

Em 1956, o cientista da computação Edsger Dijkstra formulou o algoritmo definitivo para encontrar o caminho de custo mínimo entre um nó de origem e todos os demais nós em um grafo com pesos positivos.

O algoritmo de Dijkstra substitui a fila simples do BFS por uma fila de prioridade (Priority Queue ou Min-Heap), que sempre entrega o nó não-visitado que possui a menor distância acumulada até o momento.

O mecanismo opera pelo princípio do relaxamento de arestas: Ao analisar uma aresta do nó u para o nó v com peso w, verificamos: Se distancia[u] + w < distancia[v], significa que encontramos um caminho mais curto para chegar em v passando por u. Atualizamos distancia[v] com esse novo valor menor e registramos u como o antecessor de v.

Complexidade: com uma fila de prioridade baseada em heap binária, o algoritmo de Dijkstra roda em tempo O((|V| + |E|) log |V|).

A limitação do Dijkstra

Dijkstra assume que, uma vez que um nó é retirado da fila de prioridade como o mais próximo, sua distância final está gravada em pedra e nunca mais diminuirá. Essa premissa desmorona se o grafo tiver arestas com pesos negativos: um caminho longo pode se tornar mais barato no futuro se encontrar uma aresta negativa. Para grafos com custos negativos, o algoritmo correto é o Bellman-Ford.

6. O Algoritmo A* e a matemática das heurísticas

O algoritmo de Dijkstra é brilhante e matematicamente infalível, mas ele sofre de um problema grave de desempenho em mapas gigantes: ele é completamente cego quanto à direção do objetivo.

Se você colocar o algoritmo de Dijkstra para calcular a rota de São Paulo até o Rio de Janeiro, ele expandirá ondas uniformes em todas as direções de 360 graus: ele explorará estradas em direção a Curitiba, Belo Horizonte e Campinas com o mesmo afinco com que explora a rodovia Presidente Dutra, simplesmente porque elas estão perto da origem. Ele gasta bilhões de ciclos de CPU calculando caminhos na direção oposta ao seu destino.

Em 1968, Peter Hart, Nils Nilsson e Bertram Raphael, do Instituto de Pesquisas de Stanford, resolveram essa ineficiência criando o Algoritmo A* (A-Star).

O A* pega a estrutura de fila de prioridade do Dijkstra e adiciona uma bússola matemática chamada função heurística:

f(n) = g(n) + h(n)

• g(n): o custo real exato acumulado da origem até o nó atual n (exatamente o que o Dijkstra calcula olhando para trás).
• h(n): a estimativa heurística (uma previsão calculada) do custo que ainda falta percorrer do nó atual n até o destino final (olhando para a frente).
• f(n): a pontuação total estimada do caminho que passa por n. A fila de prioridade sempre expande o nó que possui o menor f(n).

O diagrama ilustra o impacto visual dessa mudança. Enquanto o Dijkstra (à esquerda) se espalha em uma mancha circular lenta por todas as direções, o A* (à direita) usa o termo h(n) para puxar os nós na direção geométrica do alvo. O feixe de exploração afunila em direção ao destino, permitindo ignorar 80% a 95% do mapa e encontrando a rota ótima em uma fração do tempo.

Os dois extremos da heurística

Para entender a elegância do A*, repare no que acontece quando variamos o peso de h(n):

• Se h(n) = 0 para todos os nós: a fórmula vira f(n) = g(n) + 0 = g(n). O A* se degenera exatamente no Algoritmo de Dijkstra original. A heurística não ajuda, mas também não atrapalha.
• Se h(n) = h*(n) (onde h* é o custo exato real desconhecido): o A* expandirá exclusivamente os nós pertencentes à rota perfeita, caminhando em linha reta até o alvo sem visitar um único nó inútil.
• Se h(n) > h*(n): a heurística mente para cima. O algoritmo perde a garantia de encontrar o caminho mais curto.

Admissibilidade e consistência (monotonicidade)

A teoria da inteligência artificial exige duas propriedades formais para validar uma heurística:

1. Admissibilidade: A heurística h(n) é dita admissível se ela nunca superestima o custo real até o destino: h(n) ≤ h*(n), para todo n, com h(destino) = 0. A admissibilidade garante que o A* sempre encontrará o caminho ótimo se o grafo for explorado em árvore.

2. Consistência (ou Monotonicidade): Para cada nó n e cada vizinho n’ gerado por uma ação com custo c(n, n’), a estimativa deve obedecer à desigualdade triangular: h(n) ≤ c(n, n’) + h(n’). Em palavras simples: a estimativa que você tem de um ponto não pode diminuir de forma mais abrupta do que o custo real do passo que você acabou de dar. Se uma heurística for consistente, a primeira vez que o A* retira um nó da fila de prioridade, a distância g(n) calculada até ele já é garantidamente a menor possível. Isso significa que você nunca precisa reabrir ou reprocessar nós que já foram marcados como visitados, mantendo o algoritmo em velocidade máxima. Toda heurística consistente é admissível.

Catálogo de heurísticas para grades e mapas

A escolha da fórmula geométrica depende das regras físicas de movimentação permitidas no seu sistema:

1. Distância de Manhattan (Norma L1)

Usada quando o personagem ou veículo só pode se deslocar em 4 direções ortogonais (cima, baixo, esquerda, direita), sem diagonais, como carros nas ruas quadriculadas de Manhattan em Nova York: dx = |ponto.X - destino.X| dy = |ponto.Y - destino.Y| h(n) = dx + dy

2. Distância de Chebyshev (Norma L∞)

Usada quando o movimento é permitido em 8 direções e o custo de andar na diagonal é exatamente o mesmo de andar na horizontal ou vertical (como o movimento do Rei no tabuleiro de xadrez): h(n) = max(dx, dy)

3. Distância Octile

Usada em jogos e robótica onde o movimento é permitido em 8 direções, mas andar na diagonal custa a hipotenusa geométrica real (√2 ≈ 1,414) enquanto passos ortogonais custam 1,0: D1 = 1.0 (custo reto) D2 = 1.41421356 (custo diagonal) h(n) = D1 · (dx + dy) + (D2 - 2 · D1) · min(dx, dy) Essa fórmula é a mais comum em jogos de estratégia e RTS modernos.

4. Distância Euclidiana (Norma L2)

Usada quando o agente pode se mover em qualquer ângulo contínuo sem ficar preso a eixos de grades: h(n) = √((dx)² + (dy)²)

Truques avançados de engenharia no A*

1. Tie-breaking (desempate de platôs): Quando o A* navega por áreas abertas sem obstáculos, muitos nós vizinhos recebem exatamente o mesmo valor de f(n). A fila de prioridade não sabe quem escolher primeiro e começa a expandir nós em círculos desordenados, gerando um feixe largo e lento. O truque dos veteranos de jogos consiste em adicionar um pequeno viés (fator p) à heurística: h = h · (1.0 + p), onde p = 1 / 1000. Essa inclinação microscópica favorece os nós que estão mais próximos da linha reta que conecta o ponto inicial ao destino, fazendo o algoritmo cortar o mapa como uma flecha reta sem nenhum ziguezague.

2. Weighted A (A ponderado para jogos):** Em mapas com centenas de milhares de nós em jogos AAA, calcular a rota 100% perfeita consome tempo demais de CPU. O Weighted A* altera a equação para: f(n) = g(n) + ε · h(n), com ε > 1 (geralmente entre 1.2 e 2.0). O algoritmo passa a dar muito mais peso à heurística do que ao custo real acumulado, agindo como uma busca gulosa guiada. O caminho encontrado tem a garantia matemática de não ser mais longo do que ε vezes o caminho ótimo, mas a busca visita até 90% menos nós, rodando a 60 frames por segundo.

3. Heurísticas para grafos não-geométricos (sem coordenadas X e Y): Como aplicar o A* para resolver o jogo dos 8 blocos (8-puzzle), cubos mágicos ou roteamento de redes sem mapa físico? A técnica padrão chama-se relaxamento do problema: você remove regras do problema original para torná-lo fácil de resolver. No jogo dos 8 blocos, se você permitir que os números atravessem paredes e pulem uns por cima dos outros, a distância de Manhattan de cada peça até sua posição final vira uma heurística consistente e admissível espetacular. Em redes de computadores, a técnica de Landmarks (ALT: A*, Landmarks, Triangle Inequality) pré-calcula distâncias até alguns servidores de referência e usa a desigualdade triangular para estimar distâncias no grafo.

4. Variações de arquitetura de memória:

   • IDA (Iterative Deepening A):** Em vez de guardar milhões de nós em uma fila de prioridade na RAM, usa uma busca em profundidade (DFS) que corta caminhos cujo f(n) ultrapassa um teto predeterminado, aumentando o teto a cada iteração. Consome memória linear O(profundidade).
   • HPA (Hierarchical Pathfinding):* Divide o mapa do mundo em pedaços de 16x16 ou 32x32 blocos e cria um macro-grafo de portas entre os blocos, calculando a rota global primeiro e o caminho local detalhado apenas onde o jogador está pisando.

7. Outros algoritmos essenciais na teoria dos grafos

Além dos quatro grandes algoritmos de busca e caminho mínimo, todo engenheiro de software sênior precisa conhecer os seguintes clássicos do catálogo:

8. Implementação completa do Algoritmo A* em Go

Abaixo está uma implementação completa, idiomática e executável do algoritmo A* em Go para navegar em uma malha de coordenadas 2D com obstáculos:

package main

import (
	"container/heap"
	"fmt"
	"math"
)

// Ponto representa uma coordenada (x, y) na grade.
type Ponto struct {
	X, Y int
}

// ItemFila representa um elemento dentro da Min-Heap do A*.
type ItemFila struct {
	Ponto Ponto
	Prioridade float64 // f(n) = g(n) + h(n)
	Indice     int
}

// FilaPrioridade implementa heap.Interface para a Min-Heap de nós.
type FilaPrioridade []*ItemFila

func (pq FilaPrioridade) Len() int           { return len(pq) }
func (pq FilaPrioridade) Less(i, j int) bool { return pq[i].Prioridade < pq[j].Prioridade }
func (pq FilaPrioridade) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].Indice = i
	pq[j].Indice = j
}
func (pq *FilaPrioridade) Push(x any) {
	n := len(*pq)
	item := x.(*ItemFila)
	item.Indice = n
	*pq = append(*pq, item)
}
func (pq *FilaPrioridade) Pop() any {
	antigo := *pq
	n := len(antigo)
	item := antigo[n-1]
	antigo[n-1] = nil
	item.Indice = -1
	*pq = antigo[0 : n-1]
	return item
}

// heuristica calcula a Distancia de Manhattan (admissivel para 4 direcoes).
func heuristica(a, b Ponto) float64 {
	return math.Abs(float64(a.X-b.X)) + math.Abs(float64(a.Y-b.Y))
}

// AStar calcula o caminho mais curto desviando de paredes e obstaculos.
func AStar(origem, destino Ponto, grade [][]int) []Ponto {
	linhas := len(grade)
	colunas := len(grade[0])

	// gScore guarda o custo real do caminho mais curto conhecido ate cada ponto
	gScore := make(map[Ponto]float64)
	gScore[origem] = 0

	// veioDe guarda o mapa de migalhas de pao para reconstruir a rota
	veioDe := make(map[Ponto]Ponto)

	pq := make(FilaPrioridade, 0)
	heap.Init(&pq)
	heap.Push(&pq, &ItemFila{
		Ponto:      origem,
		Prioridade: heuristica(origem, destino),
	})

	visitados := make(map[Ponto]bool)

	// Movimentos possiveis: cima, baixo, esquerda, direita
	direcoes := []Ponto{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

	for pq.Len() > 0 {
		atualItem := heap.Pop(&pq).(*ItemFila)
		atual := atualItem.Ponto

		// Se atingimos o objetivo, reconstruimos a rota de tras para frente
		if atual == destino {
			caminho := []Ponto{atual}
			for p, existe := veioDe[atual]; existe; p, existe = veioDe[atual] {
				caminho = append([]Ponto{p}, caminho...)
				atual = p
			}
			return caminho
		}

		if visitados[atual] {
			continue
		}
		visitados[atual] = true

		for _, d := range direcoes {
			vizinho := Ponto{X: atual.X + d.X, Y: atual.Y + d.Y}

			// Ignora fora dos limites ou se for obstaculo (grade == 1)
			if vizinho.X < 0 || vizinho.X >= linhas || vizinho.Y < 0 || vizinho.Y >= colunas {
				continue
			}
			if grade[vizinho.X][vizinho.Y] == 1 || visitados[vizinho] {
				continue
			}

			// Custo de cada passo na grade unitaria e 1.0
			tentativaG := gScore[atual] + 1.0

			custoAnterior, registrado := gScore[vizinho]
			if !registrado || tentativaG < custoAnterior {
				veioDe[vizinho] = atual
				gScore[vizinho] = tentativaG
				fScore := tentativaG + heuristica(vizinho, destino)

				heap.Push(&pq, &ItemFila{
					Ponto:      vizinho,
					Prioridade: fScore,
				})
			}
		}
	}

	return nil // Nenhum caminho possivel encontrado
}

func main() {
	// Grade 5x5: 0 = livre, 1 = parede/obstaculo
	grade := [][]int{
		{0, 0, 0, 0, 0},
		{0, 1, 1, 1, 0},
		{0, 0, 0, 1, 0},
		{0, 1, 0, 0, 0},
		{0, 0, 0, 1, 0},
	}

	inicio := Ponto{0, 0}
	fim := Ponto{4, 4}

	rota := AStar(inicio, fim, grade)

	fmt.Printf("Caminho encontrado com sucesso (%d passos):\n", len(rota))
	for i, p := range rota {
		fmt.Printf("Passo %d: (%d, %d)\n", i, p.X, p.Y)
	}
}

9. Erros comuns e boas práticas

1. Esquecer de marcar nós como visitados. Se o grafo tiver um ciclo e você não mantiver um conjunto de visitados (visited[u] = true), tanto o BFS quanto o DFS entrarão em loop infinito até travar a CPU ou esgotar a memória da máquina.
2. Usar heurísticas não-admissíveis no A*. Se a sua heurística superestimar a distância real (por exemplo, chutando que faltam 10 km quando na verdade faltam apenas 5 km), o A* deixará de expandir caminhos que parecem caros mas que seriam os mais curtos, perdendo a garantia de encontrar a rota ótima.
3. Não prever a explosão de memória da fila de prioridade no A*. Embora o A* explore menos nós que o Dijkstra, ele precisa manter em memória a lista aberta (a fronteira de busca). Em mapas de mundo aberto gigantescos de jogos com milhões de polígonos, a memória RAM pode se esgotar rapidamente. Nesses casos, a indústria usa variações como o IDA* (Iterative Deepening A*) ou divide o mapa em grafos hierárquicos (HPA*).
4. Usar Dijkstra em grafos com pesos negativos. Como o Dijkstra nunca reavalia um nó cuja distância já foi fechada, arestas negativas geram rotas erradas e silenciosas. Se houver custos negativos (como descontos ou recarga de bateria), use obrigatoriamente Bellman-Ford.

10. Exercícios de fixação

Exercício 1: Identificação do algoritmo correto

Para cada cenário prático de engenharia de software abaixo, identifique qual algoritmo clássico de grafos deve ser utilizado:

1. Um compilador precisa determinar a ordem exata de compilação de 50 módulos de código com dependências mútuas, acusando erro se houver dependência circular.
2. Um jogo de estratégia precisa mover centenas de soldados em tempo real desviando de montanhas em direção à base inimiga.
3. Uma empresa de telecomunicações precisa interligar 20 cidades com fibra óptica pelo menor custo total de escavação e cabeamento possível.
4. Um aplicativo de mensagens precisa saber se dois usuários desconhecidos estão conectados a uma distância de até 3 graus de separação.

Resolução:

1. DFS com Ordenação Topológica (detecta ciclos e organiza a precedência linear).
2. Algoritmo A* (pathfinding direcionado e de alta performance com heurística geométrica).
3. Algoritmo de Kruskal ou Prim (Árvore Geradora Mínima / MST, conecta todos os vértices com custo total mínimo).
4. BFS (Busca em Largura limitada a profundidade 3, perfeita para contagem de saltos unitários).

Exercício 2: Detecção de ciclos em grafos direcionados com Go

Implemente uma função em Go que receba um grafo direcionado e detecte se ele possui ciclos usando o algoritmo DFS e coloração de três estados (0 = não visitado, 1 = visitando/na pilha atual, 2 = concluído).

package main

import "fmt"

type Grafo map[string][]string

// TemCiclo verifica se existe dependencia circular usando DFS.
func (g Grafo) TemCiclo() bool {
	// Estados: 0 = nao visitado, 1 = em processamento na pilha, 2 = finalizado
	estado := make(map[string]int)

	var dfs func(no string) bool
	dfs = func(no string) bool {
		estado[no] = 1 // Entra na pilha ativa

		for _, vizinho := range g[no] {
			if estado[vizinho] == 1 {
				// Encontrou um no que ja esta na pilha: ciclo detectado!
				return true
			}
			if estado[vizinho] == 0 {
				if dfs(vizinho) {
					return true
				}
			}
		}

		estado[no] = 2 // Saiu da pilha, caminho livre
		return false
	}

	for no := range g {
		if estado[no] == 0 {
			if dfs(no) {
				return true
			}
		}
	}

	return false
}

func main() {
	// Grafo com ciclo: A -> B -> C -> A
	comCiclo := Grafo{
		"A": {"B"},
		"B": {"C"},
		"C": {"A"},
	}

	// Grafo sem ciclo (DAG): A -> B -> C
	semCiclo := Grafo{
		"A": {"B"},
		"B": {"C"},
		"C": {},
	}

	fmt.Printf("Grafo 1 tem ciclo? %t\n", comCiclo.TemCiclo()) // true
	fmt.Printf("Grafo 2 tem ciclo? %t\n", semCiclo.TemCiclo()) // false
}

11. Glossário

• Vértice (Nó): Entidade individual de um grafo que armazena dados ou estados.
• Aresta: Conexão entre dois vértices, podendo ter direção e peso associado.
• Grau de um vértice: Quantidade de arestas conectadas a ele (em dígrafos, divide-se em grau de entrada e grau de saída).
• Fila de prioridade (Min-Heap): Estrutura de dados que permite extrair o elemento de menor valor em tempo logarítmico O(log n).
• Relaxamento: Ação de atualizar o caminho mais curto conhecido para um vértice ao encontrar uma rota intermediária mais barata.
• Heurística admissível: Função de estimativa que nunca prevê um custo maior do que o custo real mínimo para alcançar o objetivo.
• Árvore Geradora Mínima (MST): Subgrafo que conecta todos os vértices de um grafo ponderado sem formar ciclos e com o menor peso total de arestas.

12. Fontes e referências

• Cormen, Thomas H. et al. Introduction to Algorithms, 4ª edição, MIT Press, 2022 (Capítulo 22: Elementary Graph Algorithms, Capítulo 24: Single-Source Shortest Paths, e Capítulo 23: Minimum Spanning Trees).
• Russell, Stuart; Norvig, Peter. Artificial Intelligence: A Modern Approach, 4ª edição, Pearson, 2020 (Capítulo 3: Solving Problems by Searching - A* Search and Heuristics).
• Rosen, Kenneth H. Discrete Mathematics and Its Applications, 8ª edição, McGraw-Hill, 2019 (Capítulo 10: Graphs, e Capítulo 11: Trees). Consulta em novembro de 2026.

Relacionados

• Lógica proposicional e de primeira ordem
• Indução matemática
• Teoria dos conjuntos, relações e funções
• Teoria dos números e aritmética modular
• Análise combinatória e contagem
• Big O