Grafos e algoritmos
Capítulo 1 — Introdução
Os grafos estão presentes em muito do que diz respeito à ciência da computação. Eles são uma abstração perfeitamente computável para boa parte das relações da realidade e da imaginação humana.
Conceitualmente, um grafo é composto por um conjunto discreto de elementos que representam a existência de algo material ou imaginário. Estes elementos se relacionam; há uma regra, ou um conjunto de regras, definindo estas relações pela lógica. Em outras palavras, os elementos do conjunto discreto em questão são inter-conectados por relações de um padrão de incidência bem definido, e estas relações fazem parte do grafo — elas são expressas por arestas, enquanto os elementos inter-conectados são expressos por vértices.
Você pode inquirir por esclarecimento: a propósito, o que exatamente significa isso? Qual é a aplicação prática disso tudo? Para que estas dúvidas se façam sanadas, é conveniente que antes se conheça alguns formalismos sobre os grafos. A concepção deste universo de idéias com vértices e arestas é papel de uma teoria matemática prenunciada por Leonhard Euler em 1736, em seu artigo sobre o problema das 7 pontes de Königsberg. É a chamada teoria dos grafos.
Basicamente, a teoria dos grafos trata de relações entre elementos de conjuntos discretos. Ela é amplamente empregada em algoritmos para abstrair objetos do mundo real ou imaginário que são inter-relacionados de alguma forma.
Capítulo 2 — Teoria matemática dos grafos
2.1 Elementos de um grafo
Um Grafo é constituído por um conjunto de vértices, um conjunto de arestas e uma função de incidência.
- Os vértices são elementos, inter-relacionados de alguma forma, pertencentes a um conjunto discreto (enumerável).
- As arestas são elementos de um conjunto discreto que descrevem, de alguma forma, as relações entre os vértices do grafo.
- A função de incidência é uma função que mapeia, para cada aresta do grafo, um par de vértices envolvidos no relacionamento.
Grafos normalmente são representados graficamente por diagramas, onde os vértices são pontos e as arestas são linhas (ou setas, no caso dos dígrafos) que ligam os pontos dos respectivos vértices envolvidos no relacionamento.
No grafo da figura acima, temos um conjunto de vértices VG = {A, B, C, D}, e um conjunto de arestas aG = {1, 2, 3, 4}. A função de incidência ΨG mapeia as relações do conjunto de arestas da seguinte forma:
Estes elementos do grafo podem ter diversas interpretações. Se estivéssemos representando um mapa urbano, os vértices poderiam ser as casas e as arestas poderiam ser as vias de mão dupla que interligam estas casas. Em outro exemplo: se estivéssemos representando uma rede social, os vértices poderiam ser pessoas e as arestas poderiam ser as relações de amizade entre elas. Perceba que em ambos estes casos as relações são mútuas.
- No exemplo da rede social: Se houver uma relação de amizade entre duas pessoas, então ambas se conhecem e consideram-se amigas.
- No exemplo do mapa: Se houver uma via de mão dupla interligando duas casas, qualquer veículo pode se locomover para qualquer uma das duas casas por meio desta via.
Porém, há casos em que as relações do grafo não são mútuas. Se estivéssemos, por exemplo, representando um mapa (semelhante ao mapa do exemplo anterior), com ruas de mão única (onde os veículos só podem circular em um sentido), a ideia de relação mútua no grafo já não serviria mais. Outro exemplo: se estivéssemos representando uma rede social como o Twitter ou o Instagram, em que as relações de amizade são substituídas por relações de “seguidor” e “seguido” (e uma pessoa não é obrigada a seguir seus seguidores), a ideia de relação mútua no grafo também não serviria.
2.2 Dígrafos
O fato de que pode ser necessário representar relações não mútuas com grafos justifica a existência de duas categorias de grafos:
- Grafos não-direcionados: Grafos cujas arestas representam relações mútuas.
- Grafos direcionados (também chamados de dígrafos): Grafos cujas arestas possuem direção definida e representam relações não necessariamente mútuas.
Na representação gráfica do dígrafo, as arestas são representadas como setas que indicam uma ou duas direções, ao invés de linhas.
É possível representar um mapa com vias de mão única, ou uma rede social como o Twitter ou o Instagram, utilizando um dígrafo, por conta de suas relações, que não necessariamente são mútuas.
2.3 Grafos valorados
Grafos valorados, ou grafos ponderados, são grafos cujas arestas contêm pesos. Estes são utilizados para representar alguma caraterística escalar do relacionamento correspondente.
Os pesos podem ser utilizados para indicar uma medida de custo ou grandeza da incidência da relação correspondente. No exemplo do mapa urbano, os pesos podem representar o comprimento das vias, a dificuldade de locomoção na via, ou um produto desses dois fatores.
2.4 Grafos nulos
Por definição, um grafo é nulo quando não possui arestas (mesmo que possua vértices).
2.5 Grafos completos
Por definição, um grafo é completo quando todos os seus possíveis pares de vértices são conectados por uma aresta.
2.6 Grafos regulares
Por definição, um grafo é k-regular quando todos os seus vértices são conectados pela mesma quantidade k de arestas. Em outras palavras, se todos os vértices do grafo possuem o mesmo grau k, o grafo é um k-regular (de grau k).
2.7 Subgrafos
O conceito de subgrafo é análogo à definição de subconjunto. Suponha que, na imagem acima, o grafo da esquerda é G e o grafo da direita é H. Quando um grafo H está contido em um grafo G, diz-se que H é subgrafo de G. Em outras palavras: Se o conjunto de vértices de H é subconjunto dos vértices de G, o conjunto de arestas de H é subconjunto das arestas de G, e esses vértices estão interconectados em H da mesma forma que estão em G, então H é subgrafo de G.
2.8 Laços
Por definição, uma aresta que conecta um vértice a ele mesmo é chamada de laço.
2.9 Ciclos
Um ciclo é um grafo onde todos os pares possíveis de vértices são conectados por uma aresta, e todos os vértices possuem 2 conexões. Em outras palavras, um grafo conexo de grau 2 é, por definição, um ciclo.
Um grafo que possui um ou mais ciclos em seus subgrafos caracteriza-se por formar caminhos pelos quais é possível voltar ao vértice de partida. É necessário ter cuidado com este tipo de grafo na programação, pois os ciclos podem ser problemáticos para alguns algoritmos.
Capítulo 3 — Estruturas de dados
3.1 Estruturas de dados
Estruturas de dados (EDs) — que são o tema da abordagem deste capítulo — são basicamente formas particulares de organizar dados na memória de um computador. É bastante comum que organizações de dados compostas por elementos de conjuntos discretos e relacionamentos sejam utilizadas em programas de computador. Algoritmos como listas encadeadas e árvores binárias utilizam esta lógica para agrupar dados dispersos na memória do computador de forma que estes possam ser manipulados com alguma eficiência.
3.2 Modelos
Criar um programa de computador é um processo, e algumas etapas deste processo acontecem antes da codificação. De modo geral, uma fase de idealização do programa deve preceder a codificação, e esta fase pode ser concebida de diversas formas: Ela pode ser exercida por um engenheiro de software, por um cientista, ou pelo próprio programador, e pode ter um registro — uma lista de requisitos, um diagrama, um fluxograma ou até uma representação em linguagem matemática.
A fase de idealização do programa pode envolver a projeção de uma representação esquemática e fácil de entender do que deverá ser implementado na fase de codificação — o modelo. Aqui partimos de uma tediosa abordagem puramente teórica para algo mais “palpável”: Para uma boa parte dos algoritmos que lidam com o que chamamos de estruturas de dados, os modelos são, basicamente, grafos.
3.3 Sobre termos não muito formais
Quando se trata de algoritmos e programação de computadores, o que é conhecido como “vértice” ou “aresta” na teoria dos grafos, costuma ser chamado de “nó”, “item” ou “elemento”, mesmo porque a teoria é só uma abstração da prática, e estas aplicações não precisam estar totalmente de acordo com as definições matemáticas de grafos. Neste texto, frequentemente será usado o termo “elemento” para se referir a algo que pode ser um vértice ou uma aresta de um grafo.
3.4 EDs básicas — Listas Encadeadas e Árvores
Existem dois modelos de algoritmos baseados em grafos que são muito corriqueiros na programação de computadores:
- Listas encadeadas são frequentemente empregadas na criação de arranjos dinâmicos lineares de elementos. Este modelo de ED possibilita que dados sejam agrupados em um arranjo que admite inserções e remoções de elementos com pouco custo computacional.
- Árvores são frequentemente empregadas na criação de arranjos dinâmicos não lineares de elementos. Este modelo possibilita que dados sejam agrupados com uma regra de ordenamento definida, admitindo inserções e remoções de elementos com pouco custo. Algumas variações de árvores também podem ser utilizadas para organizar famílias de dados (é o que acontece, por exemplo, em um sistema de arquivos e diretórios).
Estes dois modelos de EDs são muito conhecidos e utilizados, tidos praticamente como conceitos básicos de ciência da computação, e suas aplicações geralmente não requerem grandes reinvenções, apenas pequenas adaptações. Ambos possuem diversas implementações disponíveis ao publico, que podem ser facilmente encontradas com rápidas buscas no Google ou no GitHub.
Estes modelos não são os únicos possíveis, nem os únicos necessários. Por mais versáteis que sejam, as vezes é — sim — necessária uma mudança radical na forma como estes são implementados ou aplicados. Também há casos nos quais é necessário que se utilize um modelo menos corriqueiro e mais específico para uma determinada aplicação, ou até mesmo que se crie um novo modelo.
3.5 Lista encadeada
Uma lista encadeada é uma estrutura de dados linear. Nela, os elementos do conjunto são associados por relações de “posterior” ou “anterior”, na intenção de criar uma espécie de fileira imaginária.
3.6 Árvore
As árvores são estruturas de dados não lineares, nas quais os elementos costumam ser associados por relações de “esquerdo”, “direito”, “inferior”, “superior”, “pai”, “filho”, “menor”, “maior”, etc. Estas estruturas formam grafos conexos e acíclicos. Quando representados graficamente, formam diagramas que remetem à estrutura física de uma árvore (da natureza), com galhos ramificados.
Capítulo 4 — Vértices e arestas em estruturas de dados
4.1 Registros, objetos e referências
Em estruturas de dados como listas encadeadas e árvores os vértices do modelo costumam ser implementados como registros ou objetos, contendo informações do elemento correspondente. Dentro desses registros ou objetos, costumam haver referências para outros elementos do mesmo conjunto: Estas referências fazem o papel das arestas do grafo.
Repare que, no algoritmo apresentado acima, a classe NodoLista define a estrutura padrão dos elementos da lista encadeada. Esta classe possui dois atributos: dado e próximo. O atributo dado deve conter uma informação qualquer (como o meu nome), e o atributo próximo deve conter uma referência para o objeto NodoLista do elemento adjacente (ou None, caso não haja elemento adjacente).
4.2 Listas de adjacências
Programar grafos fora dos moldes das listas encadeadas e árvores utilizando arranjos/registros/classes e referências nem sempre é conveniente. Uma outra maneira simples de representar um grafo em linhas de código é criar uma estrutura que contenha uma lista de adjacências para cada vértice do grafo.
Neste algoritmo, foi criado um dicionário com uma lista de adjacências para cada vértice do grafo.
O dicionário é um recurso da linguagem Python que facilita bastante nosso trabalho, pois permite que as listas de adjacências sejam indexadas com strings ao invés de números naturais, mas isso não significa que esta técnica de programação não possa ser reproduzida em outras linguagens.
Capítulo 5— Buscando elementos específicos em grafos
Imagine uma situação na qual, lidando com uma coleção de dados dispersos na memória do computador, seja necessário obter um ou mais elementos desta coleção que atendam a um determinado padrão. Isto é, categoricamente, um problema de busca, e existem duas formas conhecidas de resolvê-lo no âmbito computacional dos grafos: Busca em profundidade e busca em largura. Ambas as soluções serão explicadas.
5.1 Busca em profundidade
A busca em profundidade é uma estratégia utilizada para buscar elementos específicos em grafos. Esta técnica faz uso de funções recursivas, e funciona muito bem com grafos árvore.
A função recursiva de busca deve desempenhar o seguinte processo:
1 — Obter o elemento recebido como argumento
2 — Verificar se o elemento obtido é o elemento procurado:
- Caso seja, o escopo corrente da função recursiva deve retornar este elemento
- Caso não seja, o processo continua
3 — Obter os elementos adjacentes do elemento recebido como argumento
4 — Para cada um dos elementos adjacentes, fazer uma chamada recursiva passando o respectivo elemento como argumento
5 — Verificar se alguma das chamadas recursivas retornou o elemento procurado:
- Se sim, o escopo corrente da função recursiva deve retornar este elemento
- Se não, o escopo corrente da função recursiva deve retornar um dado que indique que o elemento buscado não foi encontrado.
Para um grafo árvore G, considere uma função de busca em profundidade R = b(E), onde E é um elemento (vértice) da árvore e R é o elemento que b(E) retornou. O procedimento de R = b(E) pode ser descrito com o seguinte fluxograma:
Para fins de demonstração, considere que estamos trabalhando com uma árvore formada por objetos de uma classe chamada NodoArvore, com os seguintes atributos:
- nome: Contém o nome de uma pessoa;
- id: Contém o número identificador da pessoa;
- menor: Contém uma referência para outro objeto com um número identificador menor (ou None, caso não haja adjacência);
- maior: Contém uma referência para outro objeto com um número identificador maior (ou None, caso não haja adjacência).
A classe NodoArvore também tem um método chamado inserir, que insere novos objetos na árvore recursivamente, e um método chamado imprimir, que imprime no prompt uma mensagem com os valores contidos no objeto para os atributos nome e id.
Veja, no próximo algoritmo, uma possível implementação para esta classe.
Podemos facilmente criar um algoritmo que acessa todos os elementos desta arvore utilizando uma função recursiva. Veja no exemplo a seguir.
A função percorrer_arvore invoca o método imprimir para cada um dos objetos da árvore, e uma lista com todos os nomes e ids da árvore é impressa (com os ids em ordem crescente).
É possível criar uma função recursiva que busca um determinado valor na árvore e retorna o objeto NodoArvore onde o valor foi encontrado.
Quando a função buscar é invocada, recebendo como argumento a raiz da árvore e um nome contido em um dos elementos desta, uma busca em profundidade é feita na arvore, e o objeto no qual o nome foi encontrado é retornado. Quando o nome não é encontrado na árvore, a função retorna None.
A busca em profundidade percorre os elementos da árvore “de cima para baixo” (ou “de baixo para cima”), em sequências de profundidade crescente ou decrescente. Quando um elemento da árvore é acessado e termina de ser avaliado pela busca, antes de verificar os outros elementos do mesmo nível da arvore, o algoritmo percorre os elementos de profundidade mais baixa ou mais alta. Este “mergulho” nos níveis da árvore (que normalmente acontece várias vezes em uma busca) termina quando, em uma de suas chamadas recursivas, a função atinge uma extremidade da árvore.
No entanto, se esta técnica for aplicada a um grafo que contenha ciclos, a recursão entrará em uma cadeia de acessos repetidos a determinados objetos da estrutura e, por fim, acontecerá uma falha conhecida como estouro de pilha (“stack overflow”, em inglês). É necessário, nestes casos, usar algum artifício para “marcar” os objetos que já foram acessados durante a busca, para que o algoritmo não verifique um objeto mais de uma vez durante a busca.
5.2 Busca em largura
A busca em largura é uma estratégia de busca em grafos na qual, após a verificação de um elemento do grafo, todos os elementos ajacentes são obtidos e verificados. Esta estratégia não possui o mesmo problema que a busca em profundidade com relação aos grafos cíclicos, embora também apresente algumas fragilidades que serão citadas mais adiante.
O artifício utilizado para desempenhar a busca em largura é um algoritmo de fila. Após o primeiro elemento do grafo ser verificado, todos os elementos adjacentes são obtidos e inseridos na fila. A execução do algoritmo prossegue em sucessivas repetições do seguinte processo:
1 — Obter (e remover da fila) o elemento que está a mais tempo na fila
2 — Verificar se o elemento obtido é o elemento procurado:
- Caso seja, a sucessão de repetições é finalizada
- Caso não seja, o processo continua
3 — Obter os elementos adjacentes do último elemento obtido
4 — Inserir na fila todos os elementos adjacentes obtidos
Para um grafo G, considere uma função de busca em largura R = b(E), onde E é um elemento (vértice) do grafo e R é o elemento que b(E) retornou. O procedimento de R = b(E) pode ser descrito com o seguinte fluxograma:
Para demonstrar esta técnica, será apresentado um algoritmo de busca em largura para o seguinte dígrafo:
Este dígrafo foi implementado com uma classe chamada Elemento, que possuí os seguintes atributos:
- Cor: Contém a cor do elemento no grafo.
- Adjacências: Contém uma lista de elementos adjacentes.
É possível implementar uma função para buscar (utilizando uma busca em largura) o elemento de uma determinada cor no grafo da seguinte forma:
A função buscar, do algoritmo 2.7, deve receber como argumento um objeto Elemento qualquer do grafo (a partir do qual a busca iniciará) e a cor do elemento procurado.
No entanto, esta implementação tem dois problemas:
1 — Caso o elemento procurado não exista no grafo, o procedimento entrará em um loop infinito, causando o travamento da aplicação.
2 — Caso o grafo seja cíclico, possivelmente ocorrerá reinserções de objetos (que já foram verificados) na fila, o que é desnecessário e implica em desperdício de memória.
Estes dois problemas podem ser corrigidos se, na implementação da função buscar, a seguinte regra for definida:
Um objeto só pode ser inserido na fila caso:
1 — Ele ainda não tenha sido verificado;
2 — Ele não esteja na fila esperando para ser verificado.
A primeira condição da regra pode ser implementada se todos os objetos verificados forem inseridos em uma lista. Neste caso, é possível saber se um objeto já foi verificado conferindo se ele está contido nesta lista.
Capítulo 6 — Problema do menor caminho
Para abrir o capítulo, uma situação cotidiana será ilustrada: Imagine que você, leitor, está saindo do trabalho ou da faculdade após um longo e chuvoso dia. A tempestade, que durante toda a tarde lhe atordoou com o barulho das fortes trovoadas e rajadas de vento, deixou para o fim do dia alguns rastros de destruição espalhados pela cidade: Causou alagamentos, acidentes, quedas de arvores e obstrução de muitas vias públicas. Este inconveniente todo culminou em longos congestionamentos nas principais avenidas da cidade (pelas quais você normalmente passa voltando para sua residência). O trânsito está terrível!
Com medo de passar horas nos lentos engarrafamentos a caminho de casa, você toma uma atitude antes de sair: Procura e instala um aplicativo em seu smartphone que irá determinar o caminho mais rápido para sua casa. Ao abrir o aplicativo, um serviço identifica sua localização por meio do GPS, obtém as informações do trânsito na região, solicita que um local de destino seja especificado e, por fim, determina a rota que você deverá seguir com seu carro para chegar em casa sem perder muito tempo nos congestionamentos.
Problema resolvido! O caminho mínimo entre sua localização atual e sua casa foi encontrado por um algoritmo de path-finding, e agora você poderá voltar para casa tranquilamente.
Este é um dos problemas que podem ser resolvidos utilizando algoritmos de busca em grafos: O problema do menor caminho (também conhecido como path-finding em inglês). Resolver este problema consiste em encontrar o caminho mais curto ou menos custoso de um vértice do grafo a outro. Existem vários algoritmos de path-finding, e neste capítulo serão brevemente abordados dois deles: O algoritmo de Dijkstra e o algoritmo A* (a-estrela).
6.1 Algoritmo de Dijsktra
O algoritmo de Dijkstra, assim como qualquer algoritmo de path-finding, deve receber, antes de começar a busca, dois parâmetros: Um elemento inicial e elemento final do grafo. O algoritmo deverá responder com uma lista encadeada constituída pelos elementos do grafo contidos no caminho mínimo entre o elemento inicial e o elemento final.
Considere a representação do algoritmo de Dijkstra como uma função C = dijkstra(Vi, Vf), onde:
- Vi é o elemento vértice inicial do caminho.
- Vf é o elemento vértice final do caminho.
- C é o caminho mínimo entre Vi e Vf.
A implementação do algoritmo de Dijkstra se assemelha em alguns aspectos à implementação de uma busca em profundidade. Tal como a busca em profundidade, o algoritmo de Dijkstra é um algoritmo iterativo, ou seja, ele desempenha a busca em um longo processo repetitivo. Em contraste com a busca em profundidade, o algoritmo de Dijkstra utiliza uma fila de prioridade ao invés de uma fila simples. A fila de prioridade é uma estrutura de agrupamento de dados na qual cada elemento é associado a um valor numérico chamado chave. A ordem na qual os elementos na fila de prioridade são obtidos e removidos ocorre de acordo com o valor chave de cada um destes elementos. No algoritmo de Dijkstra, as iterações obtêm vértices do grafo e calculam suas distâncias (ou custo acumulativo) para o vértice de origem Vi até que vértice final Vf seja encontrado. Cada vez que um vértice é obtido e tem sua distância para o Vi calculada, é inserido na fila de prioridade, e sua distância para Vi é usada como chave. Aí entra o papel da fila de prioridade: a cada iteração, para obter os próximos vértices do grafo que deverão ser analisados, o algoritmo busca o vértice na fila com menor chave (ou seja, menor distância para Vi) e obtém seus vértices adjecentes para processar. Com o auxílio de um conjunto de operações de lista encadeada, uma sequência de nós contendo vértices vai sendo gerada ao longo da execução do algoritmo e ligada de acordo com as adjacencias dos vértices. Ao fim da execução do algoritmo, quando o vértice Vf for encontrado, haverá uma lista encadeada correspondente a C (o menor caminho entre Vi e Vf).
6.2 Algoritmo A*
O algoritmo de Dijkstra é bastante custoso e pode não ser uma solução viável em algumas situações por conta do tempo que ele leva para dar uma resposta. Uma alternativa menos custosa ao algoritmo de Dijkstra é o algoritmo A* (a-star). Este algoritmo se assemelha muito ao algoritmo de Dijkstra. A diferênça do algoritmo A* para o algoritmo de Dijkstra está no fato de que o algoritmo A* usa uma heurística para otimizar o processo de busca pelo menor caminho. Esta heurística é basicamente uma estimativa da distância de um vértice V qualquer do grafo para o vértice final Vf. No algoritmo A*, a chave dos vértices na fila são calculadas como a soma da distância exata para Vi com a distância heurística para Vf. Consequentemente, o algoritmo sempre obterá para análise os vértices que provavelmente estão mais próximos de Vf em cada iteração, e precisará analisar menos vértices do que o algoritmo de Dijsktra para encontrar o caminho mínimo entre Vi e Vf.
Quanto menos errática for a heurística, menos custoso será o trabalho do algoritmo.
Referências
- Livro: Grafos — Uma Introdução, de Samuel Jurkiewicz.
- Capítulo 3 do livro: Inteligência Artificial, de Stuart Russell e Peter Norvig. Terceira edição, traduzida por Regina Célia Simille de Macedo. Editoras: Elsevier e Campus.
