grafos.md

Grafos

Um grafo é uma estrutura que representa um conjunto de vertices (ou nós) conectados entre si por arestas. As arestas podem ou não ser direcionadas dependendo do tipo do grafo.

_{Desenho de um grafo não direcionado simples}

Estrutura de dados

Existem várias formas de representar um grafo computacionalmente. Duas das mais comuns são:

Lista de Adjacências

O Grafo é um conjunto de nós e um nó é uma estrutura que contém o valor do nó em si e um conjunto de nós vizinhos. Dois nós são considerados vizinhos se eles compartilham uma aresta. Exemplo:

class Graph<T> {
  Set<Node<T>> nodes;
}

class Node<T> {
  T valor;
  Set<Node<T>> vizinhos;
}

Matriz de adjacência

Uma matriz bi-dimensional em que as linhas representam nós de origem e as colunas os de destino. Aqui cada vértice é identificado por um inteiro (índice da matriz). Existe uma aresta entre os nós i, e j se a matriz de adjacência M conter um valor M[i][j] = true.

boolean[][] grafo;

Esse modelo é interessante para grafos com até uma certa quantidade de vértices. Para grafos esparsos e com muitos vértices o modelo de lista de adjacências é mais indicado.

Busca

Para percorrer um grafo sem correr o risco de entrar em um loop infinito é necessário lembrar quais nós já foram percorridos pelo algoritmo de busca. Uma maneira de conseguir isso é associar um estado para cada nó e atualizar esse estado durante a busca.

Busca em profundidade

Na busca em profundidade os nós vizinhos são explorados recursivamente, indo em cada ramo do grafo até onde é possível, antes de voltar para trás e explorar os demais vizinhos.

_{Exemplo de execução de uma busca em profundidade (fonte)}

Implementação em Java:

void dfs(Node node) {
  node.label = DISCOVERED;
  for (Node n : node.neighbours()) {
    if (n.label != DISCOVERED) {
      dfs(n);
    }
  }
}

Busca em largura

Na busca em largura é usado uma fila para visitar todos os vizinhos antes de explorar o próximo nível.

_{Exemplo de execução de uma busca em largura (fonte)}

Implementação em Java:

void bfs(Node root) {
  Queue<Node> queue = new LinkedList<>();
  queue.add(root);

  while (!queue.isEmpty()) {
    Node current = queue.remove();
    current.label = DISCOVERED;

    for (Node n : current.neighbours()) {
      if (n.label != DISCOVERED) {
        queue.add(n);
      }
    }
  }
}