Grafos

Conceito

Um grafo é um conjunto de vértices ligados por arestas. É a generalização da árvore: sem raiz, sem hierarquia obrigatória, e — a diferença que muda tudo — com ciclos possíveis.

As dimensões que classificam um grafo, e cada uma muda o algoritmo:

• direcionado ou não — a aresta tem sentido?
• ponderado ou não — a aresta tem custo?
• cíclico ou acíclico — um DAG (acíclico direcionado) permite ordenação topológica; um grafo com ciclo não.
• conexo ou não — dá para chegar de qualquer vértice a qualquer outro?

As duas representações, e como escolher:

A escolha é sobre densidade. Grafos do mundo real são quase sempre esparsos (E ≈ V, não V²) — um usuário tem 200 amigos, não 2 bilhões. Por isso lista de adjacência é o padrão, e matriz é a exceção (grafos pequenos, ou algoritmos que consultam arestas aleatoriamente).

BFS vs DFS — não são "duas formas de percorrer", são ferramentas para perguntas diferentes:

Regra prática: "menor caminho" → BFS. "existe caminho / que ordem / tem ciclo" → DFS. (Menor caminho ponderado não é nenhum dos dois: é Dijkstra.)

Detectar ciclo com DFS exige três estados, não dois: não visitado, na pilha atual (cinza), terminado (preto). Encontrar um vértice cinza significa ciclo. Encontrar um preto significa apenas que você já passou por lá por outro caminho.

Em Go

A lista de adjacência idiomática é map[T][]T. Não há biblioteca de grafos na stdlib e raramente é necessária:

g := map[string][]string{
	"a": {"b", "c"},
	"b": {"d"},
}

map[T]map[T]bool quando você precisa de "existe aresta?" em O(1), ou de remoção de aresta.

Onde grafos aparecem no seu dia com Go, concretamente:

• go mod graph imprime literalmente o grafo de dependências do módulo, uma aresta por linha. É um DAG, e o resolvedor de versões faz travessia nele.
• importação circular é um erro de compilação — o compilador de Go detecta ciclo no grafo de pacotes e recusa. É a razão pela qual arquitetura em camadas é imposta pela linguagem, não só por convenção.
• ordenação topológica é o que o go build faz para decidir a ordem de compilação dos pacotes.
• go/ast produz uma árvore; o grafo de chamadas (callgraph) é um grafo.

Detalhe de implementação em Go: para DFS recursivo, o mapa de visitados como map[T]bool é o padrão. Para os três estados da detecção de ciclo, map[T]int ou dois mapas. E a ordenação topológica sai de graça da DFS: empilhe o vértice na pós-ordem e inverta o resultado.

Respostas às perguntas-guia

1. Lista de adjacência vs matriz de adjacência: quando cada uma vale?

Conceito: lista para esparso (O(V+E) de espaço), matriz para denso ou quando você precisa de "existe aresta?" em O(1).

Em Go: map[T][]T é lista; map[T]map[T]bool te dá o O(1) da matriz sem gastar V² (é uma matriz esparsa). Matriz de verdade ([][]bool) só para grafos pequenos e fixos.

2. Qual a diferença prática entre BFS e DFS, e quando cada um é o certo?

Conceito: BFS explora por distância e acha o menor caminho em número de arestas; DFS vai fundo e serve para ciclo, ordem topológica e componentes.

Em Go: BFS com slice como fila (fila = fila[1:] — e aqui o vazamento da 5. Fila importa menos porque a fila é efêmera); DFS recursivo com mapa de visitados. Para grafos enormes, DFS iterativo com pilha explícita evita depender da stack.

3. Por que grafo com ciclo exige marcar visitados e árvore não?

Conceito: árvore tem caminho único até cada nó; grafo tem caminhos múltiplos e ciclos. Sem marcação, laço infinito.

Em Go: o sintoma concreto é fatal error: stack overflow na versão recursiva — não recuperável (2. Stack vs Heap).

4. Que problema do seu trabalho é, no fundo, um grafo?

Conceito: dependências (entre módulos, tarefas, migrations), permissões e herança de papéis, rede de serviços e suas chamadas, pipelines, fluxos de estado.

Em Go: o grafo de importação dos seus pacotes. go mod graph e o erro de importação circular são os dois lugares em que a linguagem te obriga a pensar nisso.

Trade-offs

Do conceito:

• Lista de adjacência: espaço proporcional ao real, e consulta de aresta linear no grau.
• Matriz: consulta O(1) e espaço V² — inviável acima de alguns milhares de vértices.
• BFS: garante o menor caminho e paga O(largura) de memória, que pode ser enorme.
• DFS: memória O(profundidade) e não dá garantia de caminho mínimo.

Em Go:

• map[T][]T custa hash por acesso a vizinho — para grafos gigantes e estáticos, IDs inteiros + [][]int é dramaticamente mais rápido (localidade e sem hash).
• DFS recursivo é o código mais claro e depende da stack; iterativo é chato e seguro.
• O compilador impor aciclicidade no grafo de pacotes é uma restrição que compra arquitetura: você não consegue criar dependência circular entre camadas nem por acidente.

Exemplo prático

package main

import "fmt"

type Grafo map[string][]string

// DFS: existe caminho? Visitados é condição de TERMINAÇÃO, não otimização.
func alcanca(g Grafo, de, para string, visto map[string]bool) bool {
	if de == para { return true }
	if visto[de] { return false } // sem isto: laço infinito
	visto[de] = true
	for _, v := range g[de] {
		if alcanca(g, v, para, visto) { return true }
	}
	return false
}

// BFS: MENOR caminho em número de arestas
func menorCaminho(g Grafo, de, para string) []string {
	if de == para { return []string{de} }
	anterior := map[string]string{de: ""}
	fila := []string{de}
	for len(fila) > 0 {
		u := fila[0]
		fila = fila[1:]
		for _, v := range g[u] {
			if _, visto := anterior[v]; visto { continue }
			anterior[v] = u
			if v == para { // reconstrói o caminho de trás para frente
				cam := []string{v}
				for x := u; x != ""; x = anterior[x] {
					cam = append([]string{x}, cam...)
				}
				return cam
			}
			fila = append(fila, v)
		}
	}
	return nil
}

// Detecção de ciclo: TRÊS estados. Cinza = está na pilha atual.
const (
	branco = 0
	cinza  = 1
	preto  = 2
)

func temCiclo(g Grafo) (bool, string) {
	cor := map[string]int{}
	var dfs func(string) (bool, string)
	dfs = func(u string) (bool, string) {
		cor[u] = cinza
		for _, v := range g[u] {
			switch cor[v] {
			case cinza:
				return true, v // voltou a um vértice da pilha atual: ciclo
			case branco:
				if ok, w := dfs(v); ok { return true, w }
			}
			// preto: já terminado por outro caminho — não é ciclo
		}
		cor[u] = preto
		return false, ""
	}
	for u := range g {
		if cor[u] == branco {
			if ok, w := dfs(u); ok { return true, w }
		}
	}
	return false, ""
}

// Ordenação topológica: sai de graça da pós-ordem da DFS, invertida.
func topologica(g Grafo) []string {
	visto := map[string]bool{}
	var ordem []string
	var dfs func(string)
	dfs = func(u string) {
		if visto[u] { return }
		visto[u] = true
		for _, v := range g[u] { dfs(v) }
		ordem = append(ordem, u) // PÓS-ordem
	}
	for u := range g { dfs(u) }
	// inverte
	for i, j := 0, len(ordem)-1; i < j; i, j = i+1, j-1 {
		ordem[i], ordem[j] = ordem[j], ordem[i]
	}
	return ordem
}

func main() {
	// DAG: dependências entre pacotes
	dag := Grafo{
		"main":    {"api", "db"},
		"api":     {"modelo"},
		"db":      {"modelo"},
		"modelo":  {},
	}
	fmt.Println("main alcança modelo?", alcanca(dag, "main", "modelo", map[string]bool{}))
	fmt.Println("menor caminho main->modelo:", menorCaminho(dag, "main", "modelo"))
	ciclo, _ := temCiclo(dag)
	fmt.Println("DAG tem ciclo?", ciclo)
	fmt.Println("ordem de build:", topologica(dag))

	// com ciclo: o que o compilador de Go recusa
	circular := Grafo{"a": {"b"}, "b": {"c"}, "c": {"a"}}
	ciclo, onde := temCiclo(circular)
	fmt.Printf("circular tem ciclo? %v (volta em %q)\n", ciclo, onde)

	// sem marcar visitados, isto nunca terminaria:
	fmt.Println("alcança inexistente?", alcanca(circular, "a", "z", map[string]bool{}))
}

Relacionado

• 1. Árvore Binária — o caso especial: acíclico e com raiz
• 3. Travessias de Árvore — as mesmas travessias, sem precisar de visitados
• 4. Pilha e 5. Fila — semana 2, DFS e BFS são elas
• 5. Recursão — DFS recursivo e o risco de profundidade

---

Parte de Semana 03 - Estruturas de Dados II e Recursão · 00 - MOC Fundamentos de Programação