Curso Livre de Estruturas de Dados/Grafos

Grafos (Estrutura de Dados)

De acordo com a literatura, a teoria dos grafos iniciou-se na cidade de Konigsberg, atual território da Rússia no ano de 1736, pelo matemático suíço Leonhard Euler (1707-1783). Leonard foi um dos matemáticos mais proeminentes de sua época, com contribuições em diversas áreas.

Figura 1: Exemplo de um Grafo

Em seu artigo, conhecido como as Sete pontes de Königsberg, Leonhard tratou de um problema muito discutido na época, onde se perguntavam se era possível a partir de um ponto de origem, atravessar todas as pontes apenas uma vez e retornar a este mesmo ponto. A solução encontrada por Leonhard para este problema é considerada o primeiro grafo criado da história.

Um grafo é formado por um conjunto de vértices (ou nós) e um conjunto de arestas (ou arcos), e cada aresta em um grafo é especificado por um par de vértices, podendo ser direcionado, não direcionado e ponderado. Podemos usar a notação G = (V, E) | V = {v0,v1, v2, ..., vn} e E = {e0, e1, ..., en} para representar um grafo, onde V é o conjunto dos vértices e E o conjunto das arestas. O conjunto de vértices do grafo da imagem ao lado é demonstrado por {A,B,C,D,E,F,G,H}, e o conjunto de arestas é demonstrado por {(A,B), (A,D), (A,C), (C,D), (C,F), (E,G), (A,A)}.

Propriedades Básicas

Tamanho e ordem

O tamanho de um grafo é dado pela quantidade de vértices do mesmo, ou seja, pode ser encontrado pelo tamanho do conjunto V(|V|).

Já a ordem de um grafo é a quantidade de arestas que ele possui, ou seja, |E|.

G = (V, E) | V = {0, 1, 2, 3, 4}; E = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {2, 3}, {1, 2}}

Número máximo de arestas

Um grafo com V vértices tem no máximo (v/2)(v-1) arestas.

Largura

O percurso em largura também usa pilha para se auxiliar, no qual visite os vértices adjacentes, marcando-os como visitados e inserindo o vértice na pilha. Sendo assim, as diferenças dos dois percursos, é que um armazena apenas um vértice adjacente na pilha, enquanto este, armazena todos os vértices adjacentes na pilha.

Usando a representação de grafo, pode-se obter como resultado: 0, 1, 4, 2 e 3.

Subgrafos

Um sub-grafo é um conjunto de arestas (e seus vértices associados) de um grafo específico.

Caminhos

Um caminho em um grafo é uma sequência de vértices adjacentes (conectados por arestas). Um caminho simples é aquele em que todos os vértices são diferentes. Um ciclo é um caminho onde o 1° e o último vértice são os mesmos . O tamanho de um caminho é igual ao número de arestas percorridas.

Isomorfismo

Dois grafos, G e H são isomórficos de for possível organizar os identificadores dos vértices de um dos grafos tal que o conjunto de arestas se torne idêntico ao conjunto de arestas do outro grafo.

Conexão

As conexões de um grafo dependem diretamente se esse é direcionado ou não direcionado, conforme segue:

• Um grafo não direcionado P é conexo se cada par de vértices nele estiver conectado por um caminho, ou seja, é possível alcançar qualquer vértice a partir de um vértice definido.
• Um grafo direcionado (ou dirigido) G pode ser classificado em três diferentes tipos tipos de conexão:
  • Fortemente Conexo: O grafo contém um caminho direto de u para v E um caminho direto de v para u para cada par de vértices (u, v);
  • Conexo: O grafo possui um caminho de v para u OU um caminho de u para v para cada par de vértices (u, v);
  • Fracamente Conexo: o grafo é fracamente conexo se a substituição de todas as suas arestas por arestas não direcionadas produz um grafo conexo.

Grafos Cíclicos

Um grafo cíclico é chamado de árvore. Um conjunto de árvores é chamado de floresta. Uma árvores de abrangência de um grafo conectado é um subgrafo que contém todos os vértices e é uma única árvore. O mesmo acontece a floresta de abrangência.

Um grafo G com V arestas é uma árvore somente se uma das seguintes condições forem satisfeitas:

• G tem V-1 arestas e nenhum ciclo
• G tem V-1 arestas e é conectado
• Exatamente um caminho simples conecta cada par de vértices em G
• G é conectado, mas removendo qualquer aresta o desconecta.

Grafo acíclico dirigido (DAG)

Na matemática, ciência da computação , e particularmente teoria dos grafos, um grafo acíclico dirigido (GAD em português, DAG em inglês) é um grafo dirigido sem ciclos dirigidos, ou seja, este consiste em vértices e bordas (também chamados arcos), com cada borda direcionada de um vértice para outro, de modo que seguir essas direções nunca formará um laço fechado. Um grafo dirigido é um DAG se, e somente se, ele puder ser topologicamente ordenado, organizando os vértices como uma ordem linear que é consistente com todas as direções de borda. Os DAGs possuem diversas aplicações científicas e computacionais, desde biologia (evolução, árvores genealógicas, epidemiologia), sociologia e até computação.

Definições

Um grafo é formado por vértices e por bordas que conectam pares de vértices, onde estes podem ser qualquer tipo de objeto que está conectado em pares por bordas. No caso de um grafo direcionado, cada borda tem uma orientação, de um vértice a outro vértice. Um caminho em um grafo direcionado é uma sequência de bordas tendo a propriedade de que o vértice final de cada borda na sequência é o mesmo que o vértice inicial da próxima borda na sequência; um caminho forma um ciclo se o vértice inicial de sua primeira borda é igual ao vértice final de sua última borda. Um grafo acíclico dirigido é um grafo direcionado que não tem ciclos. Um vértice v de um grafo direcionado é dito ser alcançável a partir de outro vértice u quando existe um caminho que começa em você e termina em v. Como um caso especial, cada vértice é considerado alcançável a partir de si mesmo (por um caminho com bordas zero). Se um vértice pode alcançar-se através de um caminho não trivial (um caminho com uma ou mais bordas), então esse caminho é um ciclo, então outra maneira de definir grafos acíclicos direcionados é que eles são os grafos em que nenhum vértice pode alcançar-se através de um caminho não trivial.

Aplicações

• Agendamento:

Representações em DAGs de ordenações parciais tem diversas aplicações em agendamento para sistemas de tarefas com restrições de ordenamento. Uma importante classe de problemas desse tipo diz respeito à coleção de objetos que precisam ser atualizados, como as células de uma planilha depois que uma das células foi alterada, ou ficheiros de uma parte de um software depois que seu código-fonte foi alterado. Nesse contexto, um grafo de dependências é um grafo que tem um vértice para cada objeto a ser alterado e uma aresta conectando dois objetos quando quer que um deles necessite ser alterado antes do outro. Um ciclo nesse grafo é chamado de dependência circular e geralmente não é permitido porque não haveria forma de agendar consistentemente as tarefas envolvidas no mesmo. Grafos de dependência sem dependências circulares formam DAGs.

• Redes de processamento de dados:

Um grafo acíclico dirigido pode ser usado para representar uma rede de elementos de processamento. Nesta representação, os dados entram em um elemento processador através de uma de suas arestas de entrada e deixam o elemento através de uma aresta de saída.

Por exemplo, em design de circuitos eletrônicos, blocos de lógica combinatória estática podem ser representados como um sistema acíclico de portas lógicas que computa uma função de uma entrada, onde a entrada e a saída da função são representadads como bits individuais. Em geral, a saída desses blocos não pode ser usada como entrada, a não ser que seja capturada por um registrador ou elemento de estado que mantenha suas propriedades acíclicas. A esquemática de circuitos eletrônicos, tanto no papel quanto em um banco de dados, é uma forma de DAG utilizando instâncias ou componentes para formar uma referência dirigida a um componente de mais baixo nível. Os circuitos eletrônicos propriamente não são necessariamente acíclicos ou dirigidos.

Linguagens para programação de fluxos de dados descrevem sistemas de operações em cursos de dados e conexões entre as saídas de algumas operações e as entradas de outras. Essas linguagens podem ser convenientes para descrever tarefas repetitivas de processamento de dados, nas quais a mesma coleção aciclicamente conectada de operações é aplicada a inúmeros itens. Elas podem ser executadas como um algoritmo em paralelo na qual cada uma das operações é realizada por um processo paralelo assim que um conjunto de entradas se torna disponível.

Em compiladores, códigos em linha reta (sem laços ou ramos condicionais) podem ser representados por um DAG que descreve as entradas e saídas de cada uma das operações aritméticas realizadas no código. Essa representação permite que o compilador realize uma eliminação de sub-expressão em comum eficientemente. Em um alto nível de organização de código, o princípio de dependências acíclicas postula que dependências entre módulos ou componentes de um grande sistema de software deveria formar um DAG.

Redes neurais com retro-alimentação são outro exemplo.

• Estruturas causais:

Grafos nos quais os vértices representam eventos ocorrendo em um tempo definido e suas arestas estão sempre apontadas de um vértice representando o momento temporal anterior a outro mais tardio são necessariamente dirigidos e acíclicos. A falta de um ciclo se dá pois o tempo associado a um vértice é sempre incrementado independentemente do caminho escolhido, então não há como "voltar” a um vértice que ficou pelo caminho. Isso reflete nossa intuição natural que causalidade significa que eventos podem afetar apenas o futuro, nunca o passado, e portanto não existem laços causais. Um erxemplo desse tipo de DAG são aqueles encontrados na abordagem de conjuntos causais à gravitação quântica - neste caso, todavia, os grafos considerados são transitivamente completos. No caso de históricos de versionamento, cada versão do software é associada a um momento único no tempo, tipicamente o momento no qual a versão foi salva, cometida ou lançada. Para grafos de citação, os documentos são publicados em um momento e só podem referenciar outros mais antigos.

Algumas vezes os eventos não estão associados a um momento específico no tempo físico. Dado que pares de eventos predispõem de uma relação puramente causal, que suas arestas representam relações causais entre os eventos, temos então um DAG. Por exemplo, uma rede Bayesiana representa um sistema de eventos probabilísticos como vértices em um DAG, no qual a verossimilhança de um exemplo pode ser calculada a partir da verossimilhança de seus precessessores no DAG. Nesse contexto, o grafo moral de um DAG é o grafo não-dirigido criado através da adição de uma aresta não-dirigida entre todos os pais do mesmo vértice (algumas vezes chamado de casamento), e então suas arestas dirigidas são substituídas por arestas não-dirigidas. Outro tipo de grafo com uma estrutura causal similar é um diagrama de influência, onde os vértices representam ou decisões a serem tomadas ou informação desconhecida e as arestas representam influências causais de um vértice a outro. Em epidemiologia, por exemplo, esses diagramas são comumente utilizados para estimar o valor esperado para diferentes escolhas para intervenção.

O contrário também é verdadeiro: que em qualquer aplicação representada por um DAG há uma estrutura causal, seja ela uma ordenação temporal como aquela mencionada no exemplo ou uma ordenação que pode ser derivada de uma estrutura de grafo. Isso se dá devido à ordenação topological de todo DAG, isto é, há pelo menos uma forma de posicionar os vértices em uma ordem na qual todos eles apontem na mesma direção ao longo de tal ordem.

• Genealogia e histórico de versões
• Grafos de citação
• Compressão de dados

Densidade

A densidade de um grafo é dada por (2*|E|)/|V|. Um grafo é denso se |E| é proporcional à |V|^2  e esparso se não.

Bipartição

Um grafo bipartido é tal que seus vértices podem ser divididos em 2 conjuntos em que todas as arestas conectam um vértice de um conjunto com um vértice de outro conjunto.

Dígrafos

Um grafo direcionado é aquele em que as arestas contém uma direção (são pares ordenados do tipo (a0, a1) => a0 -> a1). Exemplo: G = (E, V)| E = {0,1,2,3,4}; V = {(0,1), (0,2), (3,0), (0,4), (2,4)}.

Exemplos:

• Malha de transporte urbano (ruas possuem um sentido)
• Pessoa A segue pessoa B no Instagram (mas o contrário nem

sempre é verdadeiro)

Alguns autores usam o termo arco para as arestas de um grafo dirigido

Representações de Grafos

Figura 2: Ilustração de grafo

Os grafos podem ser representados de várias maneiras, porém há uma maneira de representação mais comum dentre as existentes, em forma de lista. Onde destaca-se o estado e seu peso, mostrando o estado "atual" e seu próximo estado.

Como na imagem ao lado, a representação pode ser feita como:

[ [1,2], [1,5], [2,5], [2,3], [3,4], [4,5], [4,6] ].

As outras representações podem ser feitas através de uma matriz ou listas de adjacência.

Matriz de Adjacência

Dado um grafo G = (V, E), essa representação e implementada utilizando um array de 2 dimensões de tamanho |V|x|V|. Seja essa Matriz A[|V|][|V|], uma posição A[i][j] == 1 indica que existe uma aresta do vértice i para o vértice j. Para grafos não direcionados essa adjacência é sempre simétrica. Essa técnica também pode ser utilizada para grafos ponderados, pois de A[i][j] = K, então existe uma aresta de peso K ente os vértices i e j.

Pros: fácil de implementar. Remover e buscar uma aresta tem complexidade constante O(1).

Contras: Possui complexidade de espaço O(|V|^2) mesmo se for um grafo esparso.

Figura 3: Representação de grafos em lista de adjacência

Representação de Grafos em Matriz de Adjacência

	1	2	3	4	5	6
1	0	1	0	0	1	0
2	1	0	1	0	1	0
3	0	1	0	1	0	0
4	0	0	1	0	1	1
5	1	1	0	1	0	0
6	0	0	0	0	0	1

Matriz de incidência

A matriz de incidência representa um grafo exibindo a relação entre vértices e arestas por meio de uma matriz bidimensional M[|V|][|E|], onde o valor de M[i][j] será '0' caso a aresta j não incida no vértice i, ou será outro valor caso incida. Geralmente, utiliza-se o valor '1' para incisões, transformando a matriz de incidência em uma matriz binária. Contudo, é possível se utilizar outros valores, como naturais (por exemplo, para representar a quantidade de incisões, fazendo laços aparecerem na matriz como '2' e arestas como '1'), inteiros (representar a origem com valor negativo e o destino com valor positivo) e até mesmo racionais (representar os pesos das arestas na matriz), ficando a critério da aplicação a abordagem mais eficiente.

Representação de Grafos em Matriz de incidência

	A	B	C	D	E	F	G
1	1	1	0	0	0	0	0
2	1	0	1	1	0	0	0
3	0	0	0	1	1	0	0
4	0	0	0	0	1	1	1
5	0	1	1	0	0	1	0
6	0	0	0	0	0	0	1

Percursos em Grafos

O percurso de um grafo deve-se visitar todos os vértices do grafo, podendo executar alguma tarefa em específico (imprimir, contar, entre outros), para isso existem dois principais algoritmos de percussão: por profundidade (Deph-first search) ou largura (Breath-first search), os dois partem de um nodo escolhido arbitrariamente.

Figura 4: Representação de um grafo para exemplificação

Profundidade

Este percurso implementa uma pilha, no qual, visita um primeiro vértice adjacente e com isso ele marca este nodo como visitado e coloca-se o vértice adjacente visitado em um pilha.

Ao usar a representação de grafo e usando o percurso em profundidade poderia se obter como resultado: 0,1, 2, 3 e 4.

Ciclos

Figura 5: Exemplo de um ciclo em um grafo

Um ciclo, em teoria dos grafos, é um caminho fechado em que nenhum vértice (exceto o vértice final e inicial, que se coincidem) é repetido.

Em grafos direcionados, para um caminho configurar um ciclo, o caminho precisará conter apenas uma aresta, desde que o primeiro e último vértice se coincidem e nenhum outro se repita.

Em grafos não direcionados, para configurar um ciclo o caminho precisará de no mínimo três arestas, contendo vértices distintos.

Comprimento

O comprimento de um ciclo é o número de arestas que o caminho possui. No exemplo ao lado, o caminho (1, 2, 4, 3, 1) forma um ciclo com comprimento 4, e o caminho (6, 7, 5, 6) forma um ciclo com comprimento 3.

Um ciclo com comprimento 1, é chamado de laço (loop).

Detecção de um Ciclo

Para detectar se há ou não um ciclo em um determinado grafo, pode ser utilizado o algoritmo de busca em profundidade (DFS), onde todas arestas são exploradas a partir do vértice mais recentemente descoberto que saindo dele, ainda possui arestas que ainda não foram exploradas.

Outra alternativa é o algoritmo de busca em largura (BFS), onde a partir do vértice inicial, é explorado todos seus vértices vizinhos, e a partir deles é explorado todos vizinhos ainda inexplorados até encontrar o ciclo ou constatar que o grafo é acíclico.

Grafo Hamiltoniano e Euleriano

Grafo Hamiltoniano

Figura 5: Ciclo Hamiltoniano em um grafo.

Um grafo G pode ser considerado hamiltoniano caso contenha um ciclo hamiltoniano. Definimos um ciclo como hamiltoniano quando é possível executar um caminho hamiltoniano, onde todos os vértices do grafo são percorridos, sendo que cada vértice só aparece uma vez no caminho. Todo ciclo hamiltoniano pode ser transformado em um caminho Hamiltoniano, removendo-se uma de suas arestas. Entretanto, um caminho Hamiltoniano só pode ser estendido para um ciclo hamiltoniano se suas extremidades forem contíguas.

Um grafo que contem apenas um caminho hamiltoniano é chamado de grafo rastreável.

O adjetivo "hamiltoniano" deve-se ao matemático irlandês Sir William Rowan Hamilton (1805-1865), um dos pioneiros no desenvolvimento de um problema que envolve grafos hamiltonianos, conhecido como Problema do Caixeiro Viajante (PCV).

Grafo Euleriano

Um grafo G pode ser considerado euleriano se há um ciclo em G que contenha todas as sua arestas, um ciclo euleriano necessita que haja um caminho euleriano fechado (que começa e termina no mesmo vértice), este existe caso o caminho passe apenas uma vez por cada aresta de um grafo.

Um multigrafo M é euleriano se e somente se M é convexo e cada vértice de M tem grau par.

Implementação

Implementação base da representação com Matriz de Adjacência (C++).

grafo.hpp

#ifndef GRAFO_HPP
#define GRAFO_HPP

#include <cstdint>
#include <iostream>
#include <vector>

/**
 * Classe base de grafos utilizando a representação de Matriz adjascente.
 * 
 * @autores { Daniel B., Felipi M., Pablo H. }
 * */
class Grafo {
public:
  std::vector<std::vector<int>> matrizAdjacencia;
  bool digrafo; // Sinalizador para modo de dígrafo
  int comeco;   // posicaoição inicial para percorrer

  // Construtores e destrutor
  Grafo();
  Grafo(int32_t tamanho_maximo);
  Grafo(int32_t tamanho_maximo, bool tipo);
  ~Grafo();

  // Inserção
  void adicionaAresta(int u, int v);

  // Buscas
  void BFS(int tamanho, int posicaoicao, std::vector<bool> &visitas);
  void DFS(int tamanho);
  void DFSRecursivo(int atual, std::vector<bool> &visitas);

  // Utilidade
  inline auto pontoInicial(int posicao) -> void { Grafo::comeco = posicao; };
  void printarVetor(std::vector<int>);

  // Visualização
  void mostrar();
  friend std::ostream &operator<<(std::ostream &os, const Grafo &grafo);
};

#endif // !GRAFO_HPP

grafo.cpp

#include "grafo.hpp"
#include <algorithm>
#include <cstdint>
#include <deque>
#include <memory>

// Construtor padrão tamanho 10 e digrafo
Grafo::Grafo() {
  for (int i = 0; i < 10; i++) {
    Grafo::matrizAdjacencia.push_back({});
  }
  Grafo::digrafo = true;
}

// Construtor com tamanho dinâmico.
Grafo::Grafo(int32_t max_size) {
  // Preenche a matriz com vetores vazios.
  for (int i = 0; i < max_size; i++) {
    Grafo::matrizAdjacencia.push_back({});
  }
  Grafo::digrafo = true;
}

// Construtor com tamanho e tipo dinâmico.
Grafo::Grafo(int32_t max_size, bool digrafo) {
  for (int i = 0; i < max_size; i++) {
    Grafo::matrizAdjacencia.push_back({});
  }
  Grafo::digrafo = digrafo;
}

// Adiciona um aresta
auto Grafo::adicionaAresta(int u, int v) -> void {
  // Não permitindo self-loop caso seja um dígrafo.
  if (Grafo::digrafo && u == v)
    return;

  Grafo::matrizAdjacencia.at(u).push_back(v);
  // Caso não seja um digrafo a conexão será montada ida e volta.
  if (!Grafo::digrafo)
    Grafo::matrizAdjacencia.at(v).push_back(u);
}

// Função para printar o grafo.
auto Grafo::printarVetor(std::vector<int> relations) -> void {
  if (!relations.size()) {
    std::cout << "Sem aresta\n";
    return;
  }

  std::cout << "{ ";
  for (auto it = relations.begin(); it != relations.end(); it++)
    std::cout << *it << (it == std::prev(relations.end()) ? "" : ", ");

  std::cout << " }\n";
}

auto Grafo::DFSRecursivo(int atual, std::vector<bool> &visitado) -> void {
  visitado[atual] = true;
  std::cout << atual << ": ";

  Grafo::printarVetor(Grafo::matrizAdjacencia[atual]);

  for (int i = 0; i < Grafo::matrizAdjacencia[atual].size(); i++)
    if (visitado[Grafo::matrizAdjacencia[atual][i]] == false)
      DFSRecursivo(Grafo::matrizAdjacencia[atual][i], visitado);
}

auto Grafo::DFS(int tamanho) -> void {
  std::vector<bool> visitado(tamanho, false);
  for (int atual = 0; atual < tamanho; atual++) {
    if (!visitado[atual])
      DFSRecursivo(atual, visitado);
  }
}

auto Grafo::BFS(int tamanho, int atual, std::vector<bool> &visitado) -> void {
  std::deque<int> fila;

  // Funções utilitárias locais.
  auto printar = [](const int &n) -> void { std::cout << n << " "; };
  auto recursividade = [=, &visitado](const int &n) -> void {
    Grafo::BFS(tamanho, n, visitado);
  };

  // Se o atual vértice não tenha sido visitado, printe-o
  if (!visitado[atual]) {
    printar(atual);
    visitado[atual] = true;
  }

  // Então percorra todos os vértices conectados ao atual.
  for (int i = 0; i < Grafo::matrizAdjacencia[atual].size(); i++) {
    const int vizinho = Grafo::matrizAdjacencia[atual][i];

    // Se esse vizinho não tiver sido visitado ainda, adicione-o a fila
    if (!visitado[vizinho]) {
      visitado[vizinho] = true;
      fila.push_back(vizinho);
    }
  }

  // Printe todos os elementos da fila e chame a função com ele como os atuais.
  std::for_each(fila.begin(), fila.end(), printar);
  std::for_each(fila.begin(), fila.end(), recursividade);
}

auto Grafo::mostrar() -> void {
  int tamanho = Grafo::matrizAdjacencia.size();

  // DFS
  std::cout << "DFS" << std::endl;
  Grafo::DFS(tamanho);

  // BFS
  std::cout << "BFS" << std::endl;
  std::vector<bool> visitado(tamanho, false);
  Grafo::BFS(tamanho, Grafo::comeco, visitado);
}

// TODO: Implementar desestruturação.
Grafo::~Grafo() {}

main.cpp

#include <iostream>

#include "grafo.hpp"

// Sobrecarga do operador de <<
std::ostream &operator<<(std::ostream &os, Grafo &grafo) {
  grafo.mostrar();
  return os;
}

auto main() -> int {
  // Cria o grafo de 4 nodos 
  Grafo grafo(4, true);

  // Adiciona as conexões.
  grafo.adicionaAresta(0, 1);
  grafo.adicionaAresta(0, 2);
  grafo.adicionaAresta(1, 2);
  grafo.adicionaAresta(2, 0);
  grafo.adicionaAresta(2, 3);
  grafo.adicionaAresta(3, 3);

  // Informa qual nó é o começo.
  grafo.pontoInicial(2);

  // Printa o grafo.
  std::cout << grafo;

  return 0;
}

Execução

g++ *.cpp -I. -o graph.x
./graph.x

DFS
0: { 1, 2 }
1: { 2 }
2: { 0, 3 }
3: Sem aresta
BFS
2 0 3 1

Problema de caminhos mínimos

O problema de caminho mínimos na teoria de grafos, se conceitua em encontrar o melhor caminho entre dois nós, sendo assim, consiste na minimização do custo ou de tempo de travessia.

Para encontrar o menor caminho, deve-se primeiramente resolver os subproblemas de se chegar da origem a algum vértice entre a origem e o final, armazenando seus custos e levada para adiante, no qual, esta abordagem é conhecida como programação dinâmica.

Algoritmos de grafos

Algoritmo de Dijkstra

O algoritmo de Dijkstra é uma solução para o problema do caminho mínimo de origem única. Funciona em grafos orientados e não orientados, no entanto, todas as arestas devem ter custos não negativos. Se houver custos negativos, usa-se o algoritmo de Bellman-Ford.

O funcionamento se dá identificando, a partir do nó O, qual é o custo mínimo entre esse nó e todos os outros do grafo. No início, o conjunto S contém somente esse nó, chamado origem. A cada passo, selecionamos no conjunto de nós sobrando, o que está mais perto da origem. Depois atualizamos, para cada nó que está sobrando, a sua distância em relação à origem. Se passando pelo novo nó acrescentado, a distância ficar menor, é essa nova distância que será memorizada. Escolhido um nó como origem da busca, este algoritmo calcula, então, o custo mínimo este nó para todos os demais nós do grafo. O procedimento é iterativo, determinando, na iteração 1, o nó mais próximo do nó O, na segunda iteração, o segundo nó mais próximo do nó O, e assim sucessivamente, até que em alguma iteração todos os n sós sejam atingidos.

Exemplo de código em c++:

// Implementação do algoritmo de Dijkstra
// Teste: http://br.spoj.com/problems/ENGARRAF/

#include <iostream>
#include <list>
#include <queue>
#define INFINITO 10000000

using namespace std;

class Grafo
{
private:
	int V; // número de vértices

	// ponteiro para um array contendo as listas de adjacências
	list<pair<int, int> > * adj;

public:

	// construtor
	Grafo(int V)
	{
		this->V = V; // atribui o número de vértices

		/*
			cria as listas onde cada lista é uma lista de pairs
			onde cada pair é formado pelo vértice destino e o custo
		*/
		adj = new list<pair<int, int> >[V];
	}

	// adiciona uma aresta ao grafo de v1 à v2
	void addAresta(int v1, int v2, int custo)
	{
		adj[v1].push_back(make_pair(v2, custo));
	}

	// algoritmo de Dijkstra
	int dijkstra(int orig, int dest)
	{
		// vetor de distâncias
		int dist[V];

		/*
		   vetor de visitados serve para caso o vértice já tenha sido
		   expandido (visitado), não expandir mais
		*/
		int visitados[V];

		// fila de prioridades de pair (distancia, vértice)
		priority_queue < pair<int, int>,
					   vector<pair<int, int> >, greater<pair<int, int> > > pq;

		// inicia o vetor de distâncias e visitados
		for(int i = 0; i < V; i++)
		{
			dist[i] = INFINITO;
			visitados[i] = false;
		}

		// a distância de orig para orig é 0
		dist[orig] = 0;

		// insere na fila
		pq.push(make_pair(dist[orig], orig));

		// loop do algoritmo
		while(!pq.empty())
		{
			pair<int, int> p = pq.top(); // extrai o pair do topo
			int u = p.second; // obtém o vértice do pair
			pq.pop(); // remove da fila

			// verifica se o vértice não foi expandido
			if(visitados[u] == false)
			{
				// marca como visitado
				visitados[u] = true;

				list<pair<int, int> >::iterator it;

				// percorre os vértices "v" adjacentes de "u"
				for(it = adj[u].begin(); it != adj[u].end(); it++)
				{
					// obtém o vértice adjacente e o custo da aresta
					int v = it->first;
					int custo_aresta = it->second;

					// relaxamento (u, v)
					if(dist[v] > (dist[u] + custo_aresta))
					{
						// atualiza a distância de "v" e insere na fila
						dist[v] = dist[u] + custo_aresta;
						pq.push(make_pair(dist[v], v));
					}
				}
			}
		}

		// retorna a distância mínima até o destino
		return dist[dest];
	}
};

int main(int argc, char *argv[])
{
	Grafo g(5);

	g.addAresta(0, 1, 4);
	g.addAresta(0, 2, 2);
	g.addAresta(0, 3, 5);
	g.addAresta(1, 4, 1);
	g.addAresta(2, 1, 1);
	g.addAresta(2, 3, 2);
	g.addAresta(2, 4, 1);
	g.addAresta(3, 4, 1);

	cout << g.dijkstra(0, 4) << endl;

	return 0;
}

Algoritmo de Bellman-Ford

O algoritmo de Bellman-Ford resolve o problema do caminho mais curto de única origem para o caso mais geral. Diferentemente do algoritmo de Dijkstra, o algoritmo de Bellman-Ford não impõe nenhuma restrição sobre o sinal do peso das arestas, o que o torna uma solução mais genérica.

O algoritmo é dividido em 3 etapas, sendo a inicialização, onde se padroniza os valores de distância mínima para cada nó; o relaxamento, que consiste em verificar se pode ser encontrado um caminho mais curto para v passando pelo vértice u e a verificação de ciclos negativos, que se responsabiliza em verificar se é possível ou não calcular o caminho mínimo partindo do princípio que não se pode ter um ciclo negativo.

Exemplo de código em c++:

#include <iostream>
#include <vector>
#include <array>
#include <climits> // INT_MAX

using namespace std;

struct Node {
  int p = -1;
  int d = INT_MAX;
};

using edges_t = vector<array<int, 2>>;
using graph_t = vector<edges_t>;

// if a function of this type returns true, graph traversal will be interrupted
using edge_cb = bool(*)(vector<Node>&, int, int, int);

inline bool isNegativeCycle(vector<Node>& nodes, int u, int v, int w) {
  return nodes[v].d > nodes[u].d + w;
}

inline bool relaxNode(vector<Node>& nodes, int u, int v, int w) {
  // Relaxation
  if (nodes[v].d > nodes[u].d + w) {
    nodes[v].d = nodes[u].d + w;
    nodes[v].p = u;
  }

  return false;
}

// returns true if the traversal was successful
bool traverseAllEdges(const graph_t& graph, vector<Node>& nodes, edge_cb cb) {
  for (int u = 0; u < graph.size(); ++u) {
    const edges_t adjacent = graph[u];

    for (const auto& edge : adjacent) {
      int v = edge[0]; // Adjacent vertex
      int w = edge[1]; // Weight
  
      if (cb(nodes, u, v, w)) return false;
    }
  }

  return true;
}

bool bellmanFord(const graph_t& graph, int src, int dst, vector<int>& path) {
  const int len = graph.size();
  vector<Node> nodes(len);
  
  // Initialization
  for (int i = 0; i < len; ++i) {
    nodes[i] = Node();
  }
  
  nodes[src].d = 0;

  for (int i = 0; i < len; ++i) {
    traverseAllEdges(graph, nodes, relaxNode);
  }

  // Check for negative-weight cycles
  // Stop, if such cycles were detected
  if (!traverseAllEdges(graph, nodes, isNegativeCycle)) return false;

  // Construct the path from src to dst
  path.push_back(dst);

  Node node = nodes[dst];

  while (node.p != -1) {
    path.insert(path.begin(), node.p);
    node = nodes[node.p];
  } 

  return true;
}

int main() {
  graph_t graph(5, edges_t(3));

  graph[0] = {{1, 6}, {3, 7}};
  graph[1] = {{2, 5}, {3, 8}, {4, -4}};
  graph[2] = {{1, -2}};
  graph[3] = {{2, -3}, {4, 9}};
  graph[4] = {{0, 2}, {2, 7}};

  vector<int> path;

  if (bellmanFord(graph, 0, 2, path)) {
    for (const int& v : path) {
      cout << v << ' ';
    }
  } else {
      cout << "negative cycle detected\n";
  }
}

Algoritmo de Johnson

O algoritmo de Johson foi criado em 1977 por Donald B. Johson, tendo como objetivo encontrar o caminho mínimo para todos os vértices de grafos que sejam esparsos, direcionados e valorados, permitindo que arestas tenham pesos negativos, porém sem existir um ciclo cuja soma dos pesos seja negativa. Para isso, adiciona-se um vértice e V arestas ao grafo, onde V = número de arestas e, então, aplica-se o algoritmo de Bellman-Ford para cada vértice do grafo, utilizando o novo vértice como origem. Após isso, retira-se os vértices e arestas adicionados anteriormente e atualiza os pesos das arestas do grafo. Então, aplica-se o algoritmo de Dijikstra em cada vértice do novo grafo.

Exemplo de código em c++:

#include<iostream>
#define INF 9999
using namespace std;
int min(int a, int b);
int cost[10][10], adj[10][10];
inline int min(int a, int b){
   return (a<b)?a:b;
}
main() {
   int vert, edge, i, j, k, c;
   cout << "Enter no of vertices: ";
   cin >> vert;
   cout << "Enter no of edges: ";
   cin >> edge;
   cout << "Enter the EDGE Costs:\n";
   for (k = 1; k <= edge; k++) { //take the input and store it into adj and cost matrix
      cin >> i >> j >> c;
      adj[i][j] = cost[i][j] = c;
   }
   for (i = 1; i <= vert; i++)
      for (j = 1; j <= vert; j++) {
         if (adj[i][j] == 0 && i != j)
            adj[i][j] = INF; //if there is no edge, put infinity
      }
   for (k = 1; k <= vert; k++)
      for (i = 1; i <= vert; i++)
         for (j = 1; j <= vert; j++)
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); //find minimum path from i to j through k
   cout << "Resultant adj matrix\n";
   for (i = 1; i <= vert; i++) {
      for (j = 1; j <= vert; j++) {
            if (adj[i][j] != INF)
               cout << adj[i][j] << " ";
      }
      cout << "\n";
   }
}

Saída:

Enter no of vertices: 3
Enter no of edges: 5
Enter the EDGE Costs:
1 2 8
2 1 12
1 3 22
3 1 6
2 3 4
Resultant adj matrix
0 8 12
10 0 4
6 14 0