Estruturas de Dados com Golang - Parte 5

18/05/202611 min de leitura

Lucas Lemos

Introdução

Na parte 1 cobrimos Listas, na parte 2 cobrimos Árvores, na parte 3 cobrimos Hash Tables e na parte 4 cobrimos Heaps e Priority Queues. Agora entramos em uma das estruturas mais versáteis da ciência da computação: Grafos.

Grafos modelam relacionamentos. Redes sociais, mapas de estradas, árvores de dependência, sistemas de recomendação e até a própria internet são grafos. Quando você precisa representar conexões entre coisas, grafos são a escolha natural.

Como mencionado no final da parte 4, grafos se conectam naturalmente com priority queues porque muitos algoritmos de grafo (como o caminho mais curto de Dijkstra) dependem delas.

Como nos artigos anteriores, mantemos a mesma interface base Container:

type Container interface {
  Empty() bool
  Size() int
  Clear()
  Values() []interface{}
  String() string
}

O que é um Grafo?

Um Grafo é uma coleção de vértices (também chamados de nós) conectados por arestas. Diferente de árvores, grafos não têm hierarquia estrita e podem conter ciclos.

graph LR
  A((A)) --- B((B))
  A --- C((C))
  B --- D((D))
  C --- D
  D --- E((E))

Terminologia principal:

Vértice (Nó): uma entidade no grafo
Aresta: uma conexão entre dois vértices
Direcionado vs Não-direcionado: arestas podem ter direção (A → B) ou ser bidirecionais (A — B)
Ponderado vs Não-ponderado: arestas podem carregar um valor de custo/distância
Adjacente: dois vértices conectados por uma aresta
Grau: número de arestas conectadas a um vértice

Tipos de Grafos

Grafo Não-direcionado

Arestas não têm direção. Se A conecta com B, então B conecta com A.

graph LR
  A((A)) --- B((B))
  B --- C((C))
  A --- C

Grafo Direcionado (Dígrafo)

Arestas têm direção. A → B não implica B → A.

graph LR
  A((A)) --> B((B))
  B --> C((C))
  C --> A

Grafo Ponderado

Arestas carregam um custo, distância ou peso.

graph LR
  A((A)) ---|5| B((B))
  B ---|3| C((C))
  A ---|10| C

Representação de Grafos

Existem duas formas comuns de representar um grafo em memória.

Lista de Adjacência

Cada vértice armazena uma lista dos seus vizinhos. Isso é eficiente em memória para grafos esparsos (poucas arestas em relação aos vértices).

flowchart LR
  subgraph AdjList["Lista de Adjacência"]
    A["A: [B, C]"]
    B["B: [A, D]"]
    C["C: [A, D]"]
    D["D: [B, C, E]"]
    E["E: [D]"]
  end

Espaço: O(V + E) onde V = vértices, E = arestas
Verificar se aresta existe: O(grau) em média
Iterar vizinhos: O(grau)

Matriz de Adjacência

Uma matriz 2D onde matrix[i][j] indica uma aresta entre o vértice i e o vértice j. Melhor para grafos densos.

flowchart TD
  subgraph Matrix["Matriz de Adjacência"]
    M["    A B C D E
    A [ 0 1 1 0 0 ]
    B [ 1 0 0 1 0 ]
    C [ 1 0 0 1 0 ]
    D [ 0 1 1 0 1 ]
    E [ 0 0 0 1 0 ]"]
  end

Espaço: O(V²)
Verificar se aresta existe: O(1)
Iterar vizinhos: O(V)

Quando usar qual

Operação	Lista de Adjacência	Matriz de Adjacência
Espaço	O(V + E)	O(V²)
Adicionar aresta	O(1)	O(1)
Remover aresta	O(grau)	O(1)
Verificar aresta	O(grau)	O(1)
Iterar vizinhos	O(grau)	O(V)

Use lista de adjacência para grafos esparsos (a maioria dos grafos do mundo real). Use matriz de adjacência quando precisar de verificação rápida de arestas e o grafo for denso.

Implementação prática em Go (Graph)

Vamos implementar uma representação por lista de adjacência com suporte a arestas ponderadas.

type Edge struct {
  To     string
  Weight int
}

type Graph struct {
  vertices map[string][]Edge
  directed bool
}

func NewGraph(directed bool) *Graph {
  return &Graph{
    vertices: make(map[string][]Edge),
    directed: directed,
  }
}

func (g *Graph) Empty() bool {
  return len(g.vertices) == 0
}

func (g *Graph) Size() int {
  return len(g.vertices)
}

func (g *Graph) Clear() {
  g.vertices = make(map[string][]Edge)
}

func (g *Graph) Values() []interface{} {
  result := make([]interface{}, 0, len(g.vertices))
  for v := range g.vertices {
    result = append(result, v)
  }
  return result
}

func (g *Graph) String() string {
  return fmt.Sprintf("%v", g.vertices)
}

func (g *Graph) AddVertex(v string) {
  if _, exists := g.vertices[v]; !exists {
    g.vertices[v] = []Edge{}
  }
}

func (g *Graph) AddEdge(from, to string, weight int) {
  g.AddVertex(from)
  g.AddVertex(to)

  g.vertices[from] = append(g.vertices[from], Edge{To: to, Weight: weight})

  if !g.directed {
    g.vertices[to] = append(g.vertices[to], Edge{To: from, Weight: weight})
  }
}

func (g *Graph) Neighbors(v string) []Edge {
  return g.vertices[v]
}

func (g *Graph) HasEdge(from, to string) bool {
  for _, edge := range g.vertices[from] {
    if edge.To == to {
      return true
    }
  }
  return false
}

func (g *Graph) Vertices() []string {
  keys := make([]string, 0, len(g.vertices))
  for k := range g.vertices {
    keys = append(keys, k)
  }
  return keys
}

Import usado:

import "fmt"

Travessia de Grafos

Travessia significa visitar todos os vértices de um grafo sistematicamente. As duas abordagens fundamentais são BFS e DFS.

Busca em Largura (BFS)

BFS explora o grafo nível por nível. Visita todos os vizinhos do vértice atual antes de ir mais fundo. Usa uma fila.

flowchart TD
  A["Começa na origem"] --> B["Adiciona na fila"]
  B --> C["Enquanto fila não vazia"]
  C --> D["Remove vértice da fila"]
  D --> E["Processa vértice"]
  E --> F["Enfileira vizinhos não visitados"]
  F --> C

BFS é ideal para:

Encontrar caminho mais curto em grafos não-ponderados
Travessia por níveis
Encontrar todos os vértices a k arestas de distância

func (g *Graph) BFS(start string) []string {
  visited := make(map[string]bool)
  result := []string{}
  queue := []string{start}

  visited[start] = true

  for len(queue) > 0 {
    vertex := queue[0]
    queue = queue[1:]

    result = append(result, vertex)

    for _, edge := range g.vertices[vertex] {
      if !visited[edge.To] {
        visited[edge.To] = true
        queue = append(queue, edge.To)
      }
    }
  }

  return result
}

Busca em Profundidade (DFS)

DFS explora o mais fundo possível antes de voltar. Segue um caminho até não poder continuar, então retorna para explorar outros ramos. Usa uma pilha (ou recursão).

flowchart TD
  A["Começa na origem"] --> B["Marca como visitado"]
  B --> C["Processa vértice"]
  C --> D["Para cada vizinho não visitado"]
  D --> E["DFS recursivamente"]
  E --> D

DFS é ideal para:

Detectar ciclos
Ordenação topológica
Encontrar componentes conexos
Resolver labirintos

func (g *Graph) DFS(start string) []string {
  visited := make(map[string]bool)
  result := []string{}

  g.dfsRecursive(start, visited, &result)

  return result
}

func (g *Graph) dfsRecursive(vertex string, visited map[string]bool, result *[]string) {
  visited[vertex] = true
  *result = append(*result, vertex)

  for _, edge := range g.vertices[vertex] {
    if !visited[edge.To] {
      g.dfsRecursive(edge.To, visited, result)
    }
  }
}

Versão iterativa usando pilha explícita:

func (g *Graph) DFSIterative(start string) []string {
  visited := make(map[string]bool)
  result := []string{}
  stack := []string{start}

  for len(stack) > 0 {
    vertex := stack[len(stack)-1]
    stack = stack[:len(stack)-1]

    if visited[vertex] {
      continue
    }

    visited[vertex] = true
    result = append(result, vertex)

    neighbors := g.vertices[vertex]
    for i := len(neighbors) - 1; i >= 0; i-- {
      if !visited[neighbors[i].To] {
        stack = append(stack, neighbors[i].To)
      }
    }
  }

  return result
}

BFS vs DFS

Aspecto	BFS	DFS
Estrutura de dados	Fila	Pilha/Recursão
Complexidade de espaço	O(V) pior caso	O(V) pior caso
Caminho mais curto (não-ponderado)	Sim	Não
Uso de memória	Maior para grafos largos	Maior para grafos profundos
Caso de uso	Travessia por nível, caminho mais curto	Detecção de ciclo, ordenação topológica

Caminho Mais Curto: Algoritmo de Dijkstra

O algoritmo de Dijkstra encontra o caminho mais curto de um vértice origem para todos os outros vértices em um grafo ponderado com pesos não-negativos.

É aqui que as priority queues da parte 4 entram. Dijkstra usa um min-heap para sempre processar o vértice com a menor distância conhecida.

flowchart TD
  A["Inicializa distâncias como infinito"] --> B["Define distância da origem como 0"]
  B --> C["Adiciona origem na priority queue"]
  C --> D["Enquanto fila não vazia"]
  D --> E["Extrai vértice com menor distância"]
  E --> F["Para cada vizinho"]
  F --> G{"nova distância < atual?"}
  G -->|Sim| H["Atualiza distância"]
  H --> I["Adiciona na fila"]
  I --> F
  G -->|Não| F
  F --> D

Por que funciona

Dijkstra é um algoritmo guloso. Ele sempre escolhe o vértice não visitado com a menor distância. Como todos os pesos de aresta são não-negativos, uma vez que um vértice é processado, sua menor distância é final.

Implementação prática em Go

type DijkstraResult struct {
  Distance map[string]int
  Previous map[string]string
}

type pqItem struct {
  vertex   string
  distance int
}

type minHeap []pqItem

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].distance < h[j].distance }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *minHeap) Push(x interface{}) {
  *h = append(*h, x.(pqItem))
}

func (h *minHeap) Pop() interface{} {
  old := *h
  n := len(old)
  item := old[n-1]
  *h = old[:n-1]
  return item
}

func (g *Graph) Dijkstra(start string) DijkstraResult {
  dist := make(map[string]int)
  prev := make(map[string]string)

  for v := range g.vertices {
    dist[v] = math.MaxInt
  }
  dist[start] = 0

  pq := &minHeap{{vertex: start, distance: 0}}
  heap.Init(pq)

  processed := make(map[string]bool)

  for pq.Len() > 0 {
    item := heap.Pop(pq).(pqItem)
    u := item.vertex

    if processed[u] {
      continue
    }
    processed[u] = true

    for _, edge := range g.vertices[u] {
      alt := dist[u] + edge.Weight

      if alt < dist[edge.To] {
        dist[edge.To] = alt
        prev[edge.To] = u
        heap.Push(pq, pqItem{vertex: edge.To, distance: alt})
      }
    }
  }

  return DijkstraResult{Distance: dist, Previous: prev}
}

func (r DijkstraResult) PathTo(target string) []string {
  path := []string{}
  current := target

  for current != "" {
    path = append([]string{current}, path...)
    current = r.Previous[current]
  }

  return path
}

Imports adicionais:

import (
  "container/heap"
  "math"
)

Complexidade

Tempo: O((V + E) log V) com um heap binário
Espaço: O(V) para os maps de distância e predecessor

Limitações

Dijkstra não funciona com pesos de aresta negativos. Para isso, você precisaria de Bellman-Ford (que é mais lento com O(V * E)).

Detecção de Ciclos

Detectar ciclos é uma operação comum em grafos, especialmente importante para resolução de dependências e detecção de deadlock.

Em Grafos Direcionados

Use DFS com três estados: não visitado, visitando (no caminho atual), visitado (completamente processado).

func (g *Graph) HasCycle() bool {
  white := make(map[string]bool) // não visitado
  gray := make(map[string]bool)  // visitando
  black := make(map[string]bool) // visitado

  for v := range g.vertices {
    white[v] = true
  }

  for v := range g.vertices {
    if white[v] {
      if g.hasCycleDFS(v, white, gray, black) {
        return true
      }
    }
  }

  return false
}

func (g *Graph) hasCycleDFS(v string, white, gray, black map[string]bool) bool {
  white[v] = false
  gray[v] = true

  for _, edge := range g.vertices[v] {
    if gray[edge.To] {
      return true
    }
    if white[edge.To] && g.hasCycleDFS(edge.To, white, gray, black) {
      return true
    }
  }

  gray[v] = false
  black[v] = true

  return false
}

Casos de uso reais

Redes sociais: amigos, seguidores, conexões
Mapas e navegação: estradas, rotas, caminhos mais curtos
Gerenciamento de dependências: dependências de pacotes, ordem de build
Web crawling: páginas e links
Sistemas de recomendação: relacionamentos usuário-item
Roteamento de rede: roteadores e conexões
IA de jogos: pathfinding em mapas de jogos

Escolhendo o algoritmo certo

Problema	Algoritmo
Visitar todos os nós	BFS ou DFS
Caminho mais curto (não-ponderado)	BFS
Caminho mais curto (ponderado, não-negativo)	Dijkstra
Caminho mais curto (pesos negativos)	Bellman-Ford
Detectar ciclos	DFS com coloração
Ordenação topológica	DFS
Árvore geradora mínima	Prim ou Kruskal

Conclusão

Grafos são uma das estruturas mais flexíveis para modelar relacionamentos. Seu poder vem da variedade de algoritmos que operam sobre eles de forma eficiente.

Neste artigo cobrimos representação de grafos (lista de adjacência vs matriz), travessia (BFS e DFS), caminho mais curto (Dijkstra) e detecção de ciclos. A priority queue da parte 4 apareceu naturalmente no algoritmo de Dijkstra.

Isso conclui nossa série de estruturas de dados. Passamos por Listas básicas, Árvores, Hash Tables, Heaps e agora Grafos. Cada estrutura otimiza padrões de acesso e operações diferentes. A habilidade chave é reconhecer qual estrutura se encaixa no seu problema.