Universidade regional de blumenau



Baixar 1,07 Mb.
Página4/12
Encontro01.07.2018
Tamanho1,07 Mb.
1   2   3   4   5   6   7   8   9   ...   12

Algoritmos clássicos de grafos


É necessário saber como cada um dos algoritmos funciona, em que tipos de grafo se aplicam e como o grafo deve ser modelado. O uso de um algoritmo no lugar de outro pode comprometer tanto o desempenho do sistema como chegar a resultados errados, ou ainda trazer informações desnecessárias (SKIENA; REVILLA, 2003, p. 237).

Diante disso, abaixo são detalhados os principais algoritmos de teoria dos grafos e suas aplicações.


      1. Busca em profundidade


O algoritmo de busca em profundidade, ou Depth First Search (DFS), é definido como uma sequência de visitações iniciando em um vértice qualquer p. O método consiste em escolher algum vértice q, ainda não visitado, adjacente a p e colocar em uma pilha. Depois de examinar p, o vértice do topo da pilha é removido e processado da mesma forma. Este procedimento é feito até que a pilha seja vazia, e portanto o algoritmo se encerra (LAU, 2007, p. 39). Um pseudocódigo do algoritmo de busca em profundidade pode ser visto no Quadro 1.

dfs(G)

para cada u em V

visitado[u] = false

para cada u em V

se visitado[u] = false

push(S, u)

enquanto S não é vazia

u = pop(S)

se visitado[u] = false

visitado[u] = true

para cada v em Adjacente(u)

se visitado[v] = false

push(S, v)


Fonte: adaptado de Gross e Yellen (2006, p. 132).

Quadro 1 – Algoritmo busca em profundidade


      1. Busca em largura


A diferença entre o algoritmo da busca em profundidade e busca em largura, ou Breadth First Search (BFS), está na estrutura de dados auxiliar utilizada. Enquanto que a primeira armazena os vértices em uma pilha, a segunda os armazena em uma fila. Basicamente na busca em largura é escolhido um vértice inicial p. O método então visita todos os vértices adjacentes a p, ainda não visitados, e os adiciona em uma fila. Quando todos os vizinhos são visitados então um vértice novo é removido da fila e processado da mesma maneira que p. O algoritmo encerra quando a fila ficar vazia (LAU, 2007, p. 43). Um pseudocódigo do algoritmo de busca em largura pode ser visto no Quadro 2.

bfs(G)

para cada u em V

visitado[u] = false

para cada u em V

se visitado[u] = false

insere(Q, u)

enquanto Q não é vazia

u = retira(Q)

para cada v em Adjacente(u)

se visitado[v] = false

insere(Q, v)

visitado[u] = true



Fonte: adaptado de Gross e Yellen (2006, p. 134).

Quadro 2 – Algoritmo busca em largura


      1. Ordenação topológica


Uma ordenação topológica é uma ordenação de todos os vértices de um grafo acíclico dirigido, sendo que, se o grafo G contém a aresta (u,v) então u aparece antes de v. Já, se o grafo não contém ciclo então esta ordenação é possível. De forma simplificada, a ordenação topológica de um grafo pode ser imaginada como uma linha horizontal onde todas as arestas orientadas vão da esquerda para a direita (CORMEN et al., 2001, p. 494). Um pseudocódigo do algoritmo de ordenação topológica pode ser visto no Quadro 3.

O pseudocódigo inicia com uma lista vazia Q e com todos os vértices marcados como não visitados. A seguir, para cada vértice ainda não visitado, é iniciada uma busca em profundidade e, ao encerrar cada vértice, o mesmo é adicionado no início da lista Q. O pseudocódigo encerra retornando a lista (CORMEN et al., 2001, p. 550).



topologica(G)

Q = {}


para cada u em V

visitado[u] = false


para cada u em V

se visitado[u] = false

dfs(u)

retorna Q


dfs(u)

visitado[u] = true

para cada v em Adjacente(u)

se visitado[v] = false

dfs(v)
insere(Q,u)


Fonte: adaptado de Cormen et al. (2001, p. 550).

Quadro 3 – Algoritmo ordenação topológica


      1. Algoritmo de Dijkstra


Segundo Goodrich e Tamassia (2004, p. 372), o algoritmo de Dijkstra é utilizado para encontrar o caminho de custo mínimo entre dois vértices em grafos com apenas pesos positivos. O caminho de custo mínimo é um caminho que, considerando os pesos das arestas como distâncias, o somatório dos pesos das arestas envolvidas no trajeto é o menor possível.

Kocay e Kreher (2005, p. 35) classificam o algoritmo de Dijkstra como um algoritmo guloso, pois a cada iteração o vértice seguinte a ser escolhido é o mais próximo. Um pseudocódigo do algoritmo de Dijkstra pode ser visto no Quadro 4.



dijkstra(G, s, d)

para cada u em V

visitado[u] = false

distancia[u] = INF


visitado[s] = true

distancia[s] = 0


insere(Q, {s, distancia[s]})

enquanto Q não é vazia

{u, dc} = retira(Q)

para cada v em V

se visitado[v] = false

novaDistancia = dc + custo[u, v]

se (novaDistancia < distancia[v])

distancia[v] = novaDistancia

insere(Q, {v, distancia[v]})
visitado[u] = true
retorna distancia[d]


Fonte: adaptado de Gross e Yellen (2006, p. 148).

Quadro 4 – Algoritmo de Dijkstra


      1. Algoritmo de Floyd-Warshall


O algoritmo de Floyd-Warshall é utilizado em problemas onde é necessário encontrar o caminho de custo mínimo entre todos os pares de vértices de um grafo. Este algoritmo também pode ser executado sobre um grafo que contém arestas com pesos negativos, mas que não há ciclos negativos (CORMEN et al., 2001, p. 629).

O algoritmo inicialmente tem uma matriz com custos infinitos entre todos os pares de vértices. Para cada dois vértices i e j, em cada etapa do algoritmo é gerada uma nova matriz com os custos mínimos entre ambos, passando por alguns vértices intermediários, e o resultado estará na última matriz. Também é possível controlar uma outra matriz, chamada matriz de roteamento, que é responsável por manter o caminho mínimo entre cada par de vértice (CORMEN et al., 2001, p. 629). Um pseudocódigo do algoritmo de Floyd-Warshall pode ser visto no Quadro 5.

No pseudocódigo é mostrada a inicialização do algoritmo, atribuindo para cada par de vértices (u, v), o custo de u até v, caso o vértice u é adjacente ao vértice v ou infinito caso não seja. A seguir para cada vértice intermediário k é verificado para cada par de vértices (u, v) se a soma da distância de u até k e de k até v é menor que a distância de u até v. Em caso verdadeiro a nova distância de u até v é atualizada (CORMEN et al., 2001, p. 635).


floyd(G)

para cada u em V

para cada v em V

se u é adjacente a v

distancia[u,v] = custo[u,v]

senão


distancia[u,v] = INF
para cada k em V

para cada u em V

para cada v em V

se (distancia[u,v] > (distancia[u,k] + distancia[k,v]))

distancia[u,v] = distancia[u,k] + distancia[k,v]


Fonte: adaptado de Cormen et al. (2001, p. 635).

Quadro 5 – Algoritmo de Floyd-Warshall


      1. Algoritmo de Bellman-Ford


Este algoritmo surge para resolver o problema de encontrar um caminho de custo mínimo de um vértice de origem a todos os demais. Um diferencial do algoritmo é que o grafo pode conter arestas com peso negativo. Entretanto, o algoritmo não consegue chegar a um resultado quando o grafo originar um ciclo de custo negativo (CORMEN et al., 2001, p. 588). Para que o algoritmo execute de forma correta é necessário que o grafo seja também dirigido, caso contrário, a passagem por uma aresta inúmeras vezes pode criar o ciclo de custo negativo (GOODRICH; TAMASSIA, 2007, p. 534). Um pseudocódigo do algoritmo de Bellman-Ford pode ser visto no Quadro 6.

O pseudocódigo inicia atribuindo infinito para a distância até cada vértice u. Em seguida atribui zero como distância até o vértice de origem s e para cada vértice i é percorrida a lista de arestas do grafo. Para cada aresta a é verificado se a soma da distância do vértice a.u e do peso da aresta é menor que a distância atual para o vértice a.v. Em caso verdadeiro a nova distância é atribuída como distância mínima até o vértice a.v (CORMEN et al., 2001, p. 588).



Ford(G, s)

para cada u em V

distancia[u] = INF

distancia[s] = 0


para i = 1 até tamanho(G)

para cada a em A

se distancia[a.v] > (distancia[a.u] + a.peso)

distancia[a.v] = (distancia[a.u] + a.peso)



Fonte: adaptado de Cormen et al. (2001, p. 588).

Quadro 6 – Algoritmo de Bellman-Ford


      1. Algoritmo de Hopcroft-Tarjan


A algoritmo de Hopcroft-Tarjan foi o primeiro a reconhecer a importância algorítmica da busca em profundidade. O núcleo do algoritmo contém como base uma busca em profundidade modificada que é utilizada para encontrar as componentes fortemente conexas de um grafo (ALSUWAIYEL, 2003, p. 273).

Uma componente fortemente conexa em um grafo é um subconjunto de vértices do grafo onde para cada vértice u e para cada vértice v, existe um caminho que vai de u até v e outro que vai de v até u, ou seja, todos os vértices de uma componente fortemente conexa são alcançáveis entre si (CORMEN et al., 2001, p. 490).



Um exemplo de um grafo e suas componentes fortemente conexas é exibido na Figura 5. Os vértices de uma mesma cor pertencem a mesma componente fortemente conexa.

Fonte: adaptado de Cormen et al. (2001, p. 553).

Figura 5 – Exemplo de um grafo e suas componentes fortemente conexas

Um pseudocódigo do algoritmo de Hopcroft-Tarjan pode ser visto no Quadro 7.



tarjan(G)

idx = 0


para cada u em V

num[u] = INF

low[u] = INF
para cada u em V

se num[u] = INF

dfs(u)
dfs(u)

num[u] = idx

low[u] = idx

idx = idx + 1


push(S, u)
para cada v em Adjacente(u)

se num[v] = INF

dfs(v)

se low[v] < low[u]



low[u] = low[v]

senao


se v esta em S

se num[v] < low[u]

low[u] = num[v]
se low[u] = num[u]

faca


v = pop(S)

insere(L, v)

enquanto u diferente de v

insere(Componentes, L)



Fonte: adaptado de Eppstein (2001).

Quadro 7 – Algoritmo de Hopcroft-Tarjan


      1. Algoritmo de Prim


O algoritmo de Prim é utilizado para encontrar uma árvore geradora de custo mínimo em um grafo G (LAU, 2007, p. 75). A árvore geradora de um grafo G é um subgrafo de G formado pelo menor número de arestas que mantém o subgrafo ainda conexo. Já, a árvore geradora de custo mínimo é a árvore geradora formada pelas arestas que, somando seus pesos, dará o menor custo total.

Inicialmente é escolhido um vértice j que constrói parcialmente uma árvore T. Une-se a T a aresta do grafo cujo peso é mínimo entre todas as demais arestas com um vértice pertencente a T e outro vértice não pertencente a T. Este processo é repetido enquanto existam vértices que possam ser inseridos em T (LAU, 2007, p. 75). A execução do algoritmo de Prim é restrita a grafos conexos (GOODRICH; TAMASSIA, 2004, p. 368). Um pseudocódigo do algoritmo de Prim pode ser visto no Quadro 8.

No pseudocódigo é mostrada a inicialização do algoritmo, atribuindo nulo para o predecessor de um vértice, infinito para a distância de um vértice u até a árvore T, e falso para o vetor naArvore, responsável por controlar se um vértice está ou não contido na árvore T. A seguir, um vértice arbitrário u é adicionado a uma fila de prioridades Q com o custo zero (GROSS; YELLEN, 2006, p. 146).

Enquanto a fila Q não estiver vazia, o primeiro vértice u é retirado, adicionado na árvore T e para cada vértice v, adjacente a u, é verificado se o custo de u até v é menor que o custo para adicionar v na árvore. Em caso positivo é definido u como predecessor de v e atualizada a distância de v até T. Ao final do algoritmo, a árvore geradora de custo mínino pode ser recuperada com os valores contidos em predecessor e distancia (GROSS; YELLEN, 2006, p. 146).



prim(G)

para cada u em V

predecessor[u] = null

distancia[u] = INF

naArvore[u] = false
u = um vertice qualquer

insere(Q, {u, 0})

enquanto Q não é vazia

{u, dc} = retira(Q)


se naArvore[u] = false

naArvore[u] = true

para cada v em Adjacente(u)

se naArvore[v] = false E custo[u, v] < distancia[v]

distancia[v] = custo[u, v]

predecessor[v] = u

insere(Q, {v, distancia[v]})


Fonte: adaptado de Gross e Yellen (2006, p. 146).

Quadro 8 – Algoritmo de Prim


      1. Algoritmo de Kruskal


O algoritmo de Kruskal é utilizado para gerar árvores geradoras de custo mínimo em grafos desconexos (KOCAY; KREHER, 2005, p. 76). Diferentemente do algoritmo de Prim, que inicia em algum vértice, o algoritmo de Kruskal inicia a partir de alguma aresta. Inicialmente cada componente de um grafo é composta por apenas um vértice. Em cada iteração a aresta de menor peso conecta duas componentes distintas. O algoritmo termina quando não é mais possível ligar nenhuma componente. O resultado é uma floresta, que é um conjunto de uma ou mais árvores (KOCAY; KREHER, 2005, p. 76). Um pseudocódigo do algoritmo de Kruskal pode ser visto no Quadro 9.

kruskal(G)

para cada u em V

predecessor[u] = u

tamanho[u] = 1


insere(Q, A)

ordena Q em ordem crescente pelo custo


k = 0

enquanto k < tamanho(G) E Q não é vazia

a = retira(Q)

se find(a.u) diferente de find(a.v)

union(a.u, a.v)

k = k + 1


find(u)

retorna raiz da arvore que contem u


union(u,v)

se tamanho[u] < tamanho[v]

predecessor[u] = v

tamanho[v] = tamanho[v] + tamanho[u]

senao

predecessor[v] = u



tamanho[u] = tamanho[u] + tamanho[v]

Fonte: adaptado de Cormen et al. (2001, p. 569).

Quadro 9 – Algoritmo de Kruskal


      1. Algoritmo de Ford-Fulkerson


A proposta do algoritmo de Ford-Fulkerson é determinar o fluxo máximo em uma rede de fluxo utilizando um método guloso (GOODRICH; TAMASSIA, 2004, p. 389). Para entender como este algoritmo funciona é necessário entender o conceito de rede de fluxo. Uma rede de fluxo é um grafo em que o valor de uma aresta é chamado de capacidade. A capacidade é o valor máximo de um produto que pode passar pela aresta (GOODRICH; TAMASSIA, 2004, p. 382).

A ideia principal é aumentar o valor de um fluxo em estágios, onde para cada etapa uma quantidade é colocada ao longo de um caminho entre a origem e o destino. O algoritmo encerra quando não existe mais um caminho para utilizar um fluxo. O resultado final é o valor máximo de fluxo de produto que pode atravessar a rede (GOODRICH; TAMASSIA, 2004, p. 389).

Além de encontrar o fluxo máximo em grafos, o algoritmo de Ford-Fulkerson pode ser aplicado juntamente com o algoritmo de Dijkstra, sendo assim possível encontrar o fluxo máximo de custo mínimo. O algoritmo de Dijkstra entra no lugar do algoritmo de busca em profundidade para gerar os caminhos onde passará o fluxo de dados, portanto é obrigatório que o grafo utilizado para a execução do algoritmo não forme nenhum ciclo com custo negativo (FLEMING; CRUTCHFIELD, 2006).

Outro problema que pode ser resolvido a partir do algoritmo de Ford-Fulkerson é o emparelhamento máximo em grafos bipartidos. Um emparelhamento é um subconjunto de arestas de um grafo que são mutuamente não adjacentes. Para a modelagem do problema é necessário adicionar dois novos vértices ao grafo. Um vértice para ser a fonte, que será ligada a todos os demais de um dos conjuntos do grafo bipartido, e outro para ser o sorvedouro, que será ligado a todos os vértices do outro conjunto (GROSS; YELLEN, 2006, p. 427). Sendo a capacidade de todas as arestas do grafo sempre igual a um, após a execução do algoritmo de Ford-Fulkerson o resultado será o emparelhamento máximo possível para o grafo bipartido dado (GROSS; YELLEN, 2006, p. 427).

Um pseudocódigo do algoritmo de Ford-Fulkerson pode ser visto no Quadro 10. O algoritmo recebe como parâmetros um grafo G, um vértice de origem s e um vértice de destino d. Inicialmente é atribuído zero como fluxo inicial entre todos os pares de vértices. A partir daí, enquanto existir um caminho C, entre a origem e o dentino, é obtida a capacidade da aresta de menor capacidade no caminho. Por fim, a capacidade é somada ao fluxo de cada aresta a que pertence ao caminho (CORMEN et al., 2001, p. 658).


fulkerson(G, s, d)

para cada vértice u em V

para cada vértice v em V

fluxo[u, v] = 0


enquanto existir caminho C entre s e d

fatual = capacidade da aresta de menor capacidade no caminho C

para cada aresta a em C

fluxo[u, v] = fluxo[u, v] + fatual

fluxo[v, u] = fluxo[v, u] – fatual


Fonte: adaptado de Cormen et al. (2001, p. 658).

Quadro 10 – Algoritmo de Ford-Fulkerson




1   2   3   4   5   6   7   8   9   ...   12


©livred.info 2017
enviar mensagem

    Página principal