Existem algoritmos que resolvem diversos problemas de grafos, dentre os quais: Menor Caminho com origem Única, Ordenação Topológia, Árvore de Cobertura Mínima, etc. Nesta matéria, falaremos sobre dois algoritmos que permitem a busca em grafos, o de Busca em Profundidade e o de Busca em Largura.
Primeiro, abordaremos o algoritmo de busca em profundidade. Como o próprio nome diz, ele se caracteriza por começar num nó raiz (selecionando algum nó como sendo a raiz, no caso de um grafo) e explora tanto quanto possível cada um dos seus ramos, antes de retroceder (backtracking).
Branco, cinza e preto são cores utilizadas como sentinelas para mostrar o estado de cada nó durante a execução do algoritmo. Branco significa que o nó ainda não foi visitado. Cinza significa que o nó está sendo processado, ou está na fila pronto para um posterior processamento. Preto significa que todos os adjancentes daquele nó já foram pintados de Cinza.
Segue abaixo o pseudocódigo do algoritmo de busca em profundidade.
Esse algoritmo pode ser aplicado para encontrar componentes conectados e fortemente conectados para realizar a ordenação topológica de um grafo e para resolver quebra-cabeças como o labirinto.
O algoritmo de busca em largura funciona da seguinte forma: começa pelo nó raiz e explora todos os nós vizinhos. Então, para cada um desses nós mais próximos, explora os seus nós vizinhos inexplorados e assim por diante, até que ele encontre o alvo da busca. O algoritmo utiliza, portanto, uma fila (FIFO - First In First Out). Em implementações típicas, nós que ainda não foram examinados por seus vizinhos são colocados num container (como, por exemplo, uma fila ou lista ligada) que é chamado de “aberto”. Uma vez examinados, são colocados num container “fechado”.
Segue abaixo o pseudocódigo do algoritmo de busca em largura.
Algumas aplicações desse algoritmo são: achar componentes conectados, achar todos os nódulos conectados a apenas um componente, achar o menor caminho entre um nó raiz e os outros nós do grafo, testar bipartição em grafos, dentre outras.
A complexidade espacial do algoritmo de busca em profundidade é bem menor que a de um algoritmo de busca em largura. Já a complexidade temporal é igual, pois é proporcional ao número de vértices somado ao número de arestas dos grafos que eles atravessam. Contudo, quando ocorrem buscas em grafos muito grandes, a busca em profundidade pode não terminar, pois o artifício de lembrar quais nós foram visitados não funciona por falta de espaço na memória. Analisando amortizadamente, temos que o custo total desses algoritmos de busca é O(V + E), sendo V a quantidade de vértices e E a quantidade de arestas.
Logo abaixo, um vídeo contendo exemplos da execução desses algoritmos.
[a]
Grafos são utilizados para modelar diversos tipos de problemas. Caso você tenha interesse, procure alguns livros ou apostilas para aprender mais. Você não vai se arrepender.
Grupo PET Computação UFCG, 2012. All rights reserved.
