Algoritmos em Grafos

Prévia do material em texto

1
I. A MATRIZ ADJACENTE E OS TAMANHOS DE UM CAMINHO 
Uma forma de interpretar o elemento da i-ésima linha e j-ésima coluna de uma matriz 
adjacente é que este representa o número de caminhos de tamanho 1 que liga vi à vj. A 
sua utilidade nos problemas de caminho está associada ao teorema: 
 
Teorema: Seja A a matriz Adjacente do grafo G. Então o elemento na i-ésima linha e j-
ésima coluna de Am representa o número de caminhos de tamanho m do vértice i para o 
vértice j. (A prova deste teorema é por indução) 
 
II. O ALGORITMO DE WARSHALL E O ALGORITMO DE FLOYD 
 
II.1. ALGORITMO DE WARSHALL 
 
É um algoritmo que tem como objetivo, com um número reduzido de cálculos, 
determinar quais os vértices que estão conectados. 
ALGORITMO DE WARSHALL 
P←A(1) 
PARA K=1 ATÉ N FAÇA 
 PARA I =1 ATÉ N FAÇA 
 PARA J=1 ATÉ N FAÇA 
 SE PI,J = 0 ENTÃO PI,J=PI,K * PK,J 
 
Este algoritmo é inicializado com a matriz adjacente modificada (P= A(1)), onde todos os 
termos maiores que 1 da matriz Adjacente (A) são trocados por 1. 
Considerando V ’como o conjunto de vértices intermediários, no estágio zero (início, onde 
P= A(1)), V’ é vazio, pois não existem vértices intermediários. Ou seja, para cada par 
ordenado de vértices (u,v), considera-se somente os arcos de (u,v). 
No primeiro estágio (K=1), para cada par ordenado de vértices consideram-se somente os 
arcos (u,v) que possuam o vértice v1 como intermediário. No próximo estágio, os 
caminhos considerados serão aqueles que passam por v1, ou v2, ou ambos. 
No comando condicional SE, verifica-se que quando pi,j é 1 já existe um caminho entre i e 
j podendo então ser desconsiderado. Entretanto, quando pi,j é 0 não existe uma ligação, 
até o momento, entre i e j verifica-se então, se o(s) vértice(s) intermediário(s) K(s) 
realiza(m) esta ligação. 
 2
II.2. ALGORITMO DE FLOYD 
 
É uma modificação do algoritmo de Warshall, que tem como objetivo calcular o caminho 
mínimo entre dois nós quaisquer em um grafo 
 
Algoritmo caminho mínimo entre todos os pares 
ENTRADA: A MATRIZ ADJACENTE COM AS MENORES ”DISTÂNCIAS” 
SAÍDA: A COM TODAS AS DISTÂNCIAS DOS CAMINHOS MÍNIMOS 
PARA K=1 ATÉ N FAÇA 
 PARA I =1 ATÉ N FAÇA 
 PARA J=1 ATÉ N FAÇA 
 SE A[I,K] +A[K,J] < A[I,J] ENTÃO A[I,J]=A[I,K]+A[K,J] 
 
 
III. O ALGORITMO DO MENOR CAMINHO (ALGORIMTO DE DIJKSTRA) 
 
Este algoritmo é um dos algoritmos que calcula o caminho de custo mínimo entre dois 
vértices de um grafo. É bastante simples e com um bom nível de performance. Ele parte 
de uma estimativa para o custo mínimo e vai sucessivamente ajustando esta estimativa. 
Um vértice é considerado fechado quando já tiver sido obtido o seu caminho de custo 
mínimo, a partir do vértice origem. Caso contrário ele é considerado aberto. 
 
Objetivo: EncontraR o valor do menor caminho entre 2 vértices onde existe um “peso”, 
custo, associado a cada arco. (O algoritmo foi construído considerando dígrafos). A 
exatidão da solução é garantida, somente quando “pesos”, não negativos, são 
considerados. 
 
Idéia Básica: Dado um vértice origem vO, encontrar o menor caminho entre vO e os outros 
vértices, até que o vértice obtido seja o vértice destino (vD). 
 
Definições: 
 
� U – conjunto de vértices mais próximos ao vértice origem; 
� dvi – distância do menor caminho entre o vO e vi 
� u – variável que representa o vértice atual. 
� tam(u,vi) – “tamanho”, “peso” do arco que liga u à vi. 
 3
� Cálculo de dvi = min{ dvi, du + tam(u, vi)}, que significa o mínimo entre dvi e (du + 
tam(u, vi), 
Algoritmo do menor caminho 
ENTRADA: G(V,E), VO, VD 
 
D(VO) ← 0 
PARA i=1 ATÉ V FAÇA 
 SE VI≠VO ENTÃO D(Vi) ←∞ 
U←VO E u←VO 
REPITA 
 PARA i = 1 ATÉ V FAÇA 
 SE (Vi ≠ u) E (u É ADJACENTE A Vi) E (Vi ∉ U) ENTÃO CALCULE D(VI) 
 MENOR_D ←∞ 
 PARA i = 1 ATÉ V FAÇA 
 SE( Vi ∉ U) E (D(Vi) < MENOR_D )ENTÃO 
 MENOR_D ←D(Vi) 
 u←Vi 
 U← U ∪ { u } 
 ATÉ QUE u= VD 
 
Este algoritmo pode ser modificado, para encontrar todos os caminhos mínimos de um 
grafo a partir de certo vértice origem. Para isso basta marcar todos os vértices como 
aberto, com exceção do vértice origem que já entra no laço principal como fechado. E 
mudar a condição do repita para até que não exista vértice aberto. 
O algoritmo do menor caminho não fornece qual o menor caminho, apenas o 
“peso”/”custo”do mesmo. Uma modificação, neste algoritmo, pode ser feita para que ele 
imprima o menor caminho. Um novo vetor é inserido (vet) e este vetor guardará os 
vértices usados para atingir o menor caminho. 
 
 
 
 
 
 4
ALGORITMO DO MENOR CAMINHO MODIFICADO 
 
(as alterações estão em negrito) 
 
ENTRADA: G(V,E), VO, VD 
 
D(VO) ← 0 
PARA i=1 ATÉ V FAÇA 
 SE VI≠VO ENTÃO D(Vi) ←∞ 
 VET[Vi]←←←←-1 
U←VO E u←VO 
REPITA 
 PARA i = 1 ATÉ V FAÇA 
 SE (Vi ≠ u) E (u É ADJACENTE A Vi) E (Vi ∉ U) E dvi> du + tam(u, vi) 
ENTÃO D(VI) ←←←← du + tam(u, vi)) 
 VET[Vi]←←←← u 
 MENOR_D ←∞ 
 PARA i = 1 ATÉ V FAÇA 
 SE( Vi ∉ U) E (D(Vi) < MENOR_D )ENTÃO 
 MENOR_D ←D(Vi) 
 u←Vi 
 U← U ∪ { u } 
 ATÉ QUE u= VD 
 
Assim no exemplo: O algoritmo do menor caminho foi executado para um grafo de 10 
vértices sendo o vértice destino v9 e o vértice origem v2. O resultado obtido foi: 
 
dv1 dv2 dv3 dv4 dv5 dv6 dv7 dv8 dv9 dv10 
3 0 ∝ 4 5 4 8 8 8 7 
 
 
vet1 vet2 vet3 vet4 vet5 vet6 vet7 vet8 vet9 vet 10 
2 -1 -1 6 6 1 5 5 10 6 
 
O valor do menor caminho seria 8 e o menor caminho seria v2→v1→v6→v10→v9. Para 
obter o menor caminho é só ler o vetor vet da posição do vértice origem até o destino. Por 
 5
exemplo, vet9=10, o que significa que para chegar em v9 passou-se por o vértice 10. Por 
sua vez vet10=6, o que significa que para chegar em v10 passou-se por o vértice 6; assim 
por diante até chegar no vértice origem. 
 
IV. ALGORITMOS DE BUSCA EM GRAFOS 
 
Encontrar caminhos entre vértices, como é efetuado com o algoritmo do menor caminho, 
é apenas um aspecto de problemas mais gerais de busca em um grafo. 
 
Existem algoritmos de busca cuja finalidade é encontrar um vértice com uma determinada 
propriedade ou com um dado (informação) específico associado a ele. 
 
Há dois métodos de busca em um grafo: busca em largura (“breadth first search, BFS”) e 
busca em profundidade (“depth first search, DFS”). 
 
IV.1. BUSCA EM LARGURA 
 
 
Neste tipo de algoritmo , a busca é realizada visitando (isto é, avaliando os dados 
associados com) os vértices mais próximos daquele que a busca foi inicializada antes de 
visitar qualquer outro. A idéia então é aplicada recursivamente. 
 
 
Embora a idéia deste algoritmo seja recursiva, a forma mais conveniente de sua 
implementação é a iterativa. Este algoritmo introduz a idéia de uma fila (estrutura linear 
onde os dados são inseridos por uma extremidade (fim) e removida pela outra (frente)). 
 
 
 
 
 
 
 
 6
BUSCA EM LARGURA 
ENTRADA: G(V,E) {UM GRAFO CONECTADO} 
SAÍDA: O RESULTADO DOS DADOS AVALIADOS EM CADA VÉRTICE 
 
MARQUE TODOS OS VÉRTICES DE V COMO “NÃO VISITADOS” {INICIALIZAÇÃO} 
ESCOLHA UM VÉRTICE V EM V 
VISITE V {VISITAR SIGNIFACA AVALIAR OS DADOS EM V} 
MARQUE V COMO “VISITADO” 
COLOQUE V EM Q {Q É UMA FILA} 
REPITA ENQUANTO Q ≠ ∅ {∅ SIGNIFICA FILA VAZIA} 
U← FRENTE (INÍCIO) Q 
PARA W ∈ A(U) {A(U) É O CONJUNTO DE VÉRTICES ADJACENTES A U} 
SE W NÃO FOI VISITADO ENTÃO 
VISITE W; MARQUE W COMO “VISITADO” 
INSIRA W NO FIM DE Q 
 FIM DO PARA 
APAGUE U DE Q {TODOS OS VIZINHOS DE U FORAM VISITADOS} 
 FIM DO REPITA 
 
Para cada vértice o laço do comando para, percorre seus vértices adjacentes. Assim cada 
arco é visitado duas vezes, uma para cada extremidade. Portanto, o tempo total do 
algoritmo é O(|V| + |E|). 
 
Note que na busca em largura: 
 
� Se G é conectado, então todos os vértices de G são visitados uma e somente uma 
vez.; 
 
� Nenhuma regraé imposta para determinar a ordem na qual os vértices adjacentes 
do atual vértice serão visitados; 
 
� Os vértices podem ser visitados à medida que forem removidos da fila; 
 
 7
A busca em largura pode ser vista como um caso especial do algoritmo do menor 
caminho onde os arcos possuem o mesmo “peso” 1. Suponha que desejamos saber o 
menor caminho entre um vértice v e todos os vértices do grafo, onde o tamanho do 
caminho é o número de arcos entre os vértices. Um exemplo prático seria um método 
para determinar o menor caminho de um ponto a outro em uma cidade onde um grafo 
representa a grade de ruas com tamanhos praticamente iguais. 
 
Para tal exemplo teríamos o algoritmo de busca em largura modificado que é denominado 
de ALGORITMO DO TAMANHO DO CAMINHO (“ALGORITHM PathLength”). Este 
algoritmo determina a menor distancia entre dois vértices somente se os pesos de todos 
os arcos são iguais. 
 
TAMANHO DO CAMINHO 
ENTRADA: G(V,E) {UM GRAFO CONECTADO} 
 V {UM DETERMINADO VÉRTICE EM V} 
 
COLOQUE V EM Q {Q É UMA FILA} 
MARQUE V CO TAMANHO 0 
REPITA ENQUANTO Q ≠ ∅ {∅ SIGNIFICA FILA VAZIA} 
U← FRENTE (INÍCIO) Q 
L←TAMANHO DO CAMINHO DE V ATÉ U 
PARA W ∈ A(U) {A(U) É O CONJUNTO DE VÉRTICES ADJACENTES A U} 
SE W NÃO ESTÁ MARCADO COM TAMANHO ENTÃO 
MARQUE W COM L+1; INSIRA W NO FIM DE Q 
 FIM DO PARA 
APAGUE U DE Q {TODOS OS VIZINHOS DE U FORAM VISITADOS} 
 FIM DO REPITA 
SAÍDA: CADA VÉRTICE MARCADO COM SEU TAMANHO DE V 
 
 
 
 
 
 8
IV.2. BUSCA EM PROFUNDIDADE 
 
Neste tipo de algoritmo, a idéia é iniciar a busca em v e ir tão longe quanto puder até que 
não haja vértices adjacentes para serem visitados. A partir daí, então, voltar no caminho 
até encontrar um vértice vizinho que não foi visitado e novamente aprofundar o caminho 
até onde der. 
 
Como no algoritmo da busca por largura, a idéia deste algoritmo é recursiva. Entretanto, a 
melhor maneira de implementá-lo é também através de um procedimento recursivo. 
 
No algoritmo abaixo é possível verificar que o este vai aumentando o caminho através da 
chamada recursiva do procedimento, toda vez que um novo vértice é obtido. Quando não 
há mais vértices a serem visitados a recursão automaticamente volta até um nível onde 
existam vértices a serem visitados. Se um vértice foi visitado, ele nunca é visitado 
novamente, portando nenhum vértice é visitado mais de uma vez. 
 
 
A busca em Profundidade é a principal idéia dos algoritmos de “backtracking” (voltar para 
trás). A essência de qualquer algoritmo de “backtracking” é efetuar a busca para uma 
determinada solução em uma direção particular até que esta seja encontrada ou algum 
tipo de fim seja alcançado. Se este fim foi alcançado então retorna-se (“backtrack”) para o 
ponto anterior mais próximo, onde alguma decisão foi tomada para a direção que 
encontrou este fim. Neste ponto, se há uma direção a seguir que ainda não foi testada, 
ela é seguida. Senão retorna-se mais para trás ainda. Assim ou a solução é encontrada, 
se existir, ou se retornará até o início com todas as possíveis direções pesquisadas. 
 
 
As principais características desta idéia são que nunca uma direção é pesquisada mais de 
uma vez e que todas as possíveis soluções são pesquisadas. 
 
 
 
 
 9
BUSCA EM PROFUNDIDADE 
 
ENTRADA: G(V,E) {UM GRAFO CONECTADO} 
SAÍDA: O RESULTADO DOS DADOS AVALIADOS EM CADA VÉRTICE 
 
PROCEDIMENTO PROF(U) {U É UM VÉRTICE} 
VISITE U 
MARQUE U COMO “VISITADO” 
PARA W ∈ A(U) {A(U) É O CONJUNTO DE VÉRTICES ADJACENTES A U} 
SE W ESTÁ MARCADO COMO NÃO VISITADO ENTÃO 
PROF(W) {CHAMADA RECURSIVA } 
 
 FIM DO PARA 
RETORNE 
 FIM DO PROCEDIMENTO 
{ALGORITMO PRINCIPAL} 
MARQUE TODOS OS VÉTICES DE V COMO NÃO VISITADOS 
ESCOLHA, ARBITRARIAMENTE, UM VÉRTICE V 
PROF(V)