Upload
cwmqueiros
View
162
Download
1
Embed Size (px)
Citation preview
1BC-0506: Comunicao e Redes
Algoritmos em Grafos
Santo Andr, 2Q2011
Parte 1: Algoritmos de Busca
3Rediscutindo: Representaes em Grafos
Matriz de Adjacncias
Matriz de Incidncias
Lista de Adjacncias
4Matriz de Adjacncias
A matriz de adjacncias de um grafo tem colunas e linhas indexadas pelos vrtices. Se A for a matriz de adjacncias de ndices i e j, A(i,j) = 1 se os vrtices i e j forem conectados por uma aresta e A(i,j) = 0 caso contrrio. Em grafos no orientados a matriz de adjacncias sempre simtrica, ou seja, A(i,j) = A(j,i).
5Exemplo: Grafo no-orientado e Matriz de Adjacncia
6Exemplo: Grafo orientado e Matriz de Adjacncia
7Matriz de Incidncia
A Matriz de Incidncia representa computacionalmente um grafo em que as linhas e colunas so vrtices e arestas. Assim, dado um grafo com n vrtices e m arestas, podemos represent-lo por uma matriz B n x m, guardando informaes sobre a incidncia de vrtices em cada aresta.
Para representar um grafo sem pesos nas arestas e no-orientado, basta que as entradas da matriz B contenham +1 se a aresta chega no vrtice, -1 se a aresta parte do vrtice e 0 caso a aresta no chegue nem parta no/do vrtice.
8Exemplo: Matriz de Incidncia
9Lista de Adjacncias
O vetor de listas de adjacncia de um grafo tem uma lista encadeada para cada um de seus vrtices. A lista de cada vrtice v contm todos os vrtices vizinhos que se pode alcanar a partir de v.
10
Exemplo: Lista de Adjacncias
Adj[1] = {2}Adj[2] = {1,3,5}Adj[3] = {4}Adj[4] = {1,5}Adj[5] = {2}
11
Grafos Ponderados
Um grafo pode ser ponderado ou no-ponderado. Se todas as arestas apresentarem um mesmo peso (ou custo), diz-se que o grafo no ponderado e considera-se todas as arestas com custo igual a 1.
O grafo ser ponderado se diferentes arestas possurem custos distintos.
12
Exemplo: Grafos Ponderados e No-Ponderados
Pode-se ainda representar um grafo no-ponderado ignorando os custos das arestas. Em um grafo no-ponderado, todas as arestas possuem custo igual a 1.
Em grafos ponderados, representa-se entre parnteses o custo da aresta.
13
Caminhos em Grafos
Um caminho num grafo uma sequncia de vrtices dotada da propriedade de que cada novo vrtice adjacente ao anterior.
A origem de um caminho o primeiro vrtice do caminho. O trmino o ltimo vrtice. Diz-se que um caminho com origem s e trmino t vai de s a t.
Dizemos que uma aresta v w pertence a um caminho se o vrtice w o sucessor de v no caminho. Todas as arestas de um caminho apontam no mesmo sentido, de um vrtice para o seu sucessor.
14
Caminhos em Grafos
Costuma-se diferenciar caminho de passeio em grafos. Assim, em um caminho de s a t, no pode haver nenhum vrtice repetido, enquanto em um passeio isso pode acontecer.
O comprimento de um caminho o nmero de termos da sequncia menos um. Em outras palavras, o nmero de arestas do caminho.
Em grafos no-orientados, a existncia de caminhos uma propriedade simtrica: para quaisquer dois vrtices s e t, existe caminho de s a t, se e somente se, existe caminho de t a s.
15
Exemplo de Caminho
Para o exemplo a seguir (no-orientado e no-ponderado), o caminho 1 a 3 deve ser passando pelo vrtice 2.
Caminho 1 a 3: 1 2 3
Caminho 3 a 1: 3 2 1
16
Exemplo de Caminho
Para grafos orientados (ponderados ou no) o caminho de s a t pode ser diferente do caminho de t a s.
Exemplo:
Caminho 1 a 3:
1 2 3
Caminho 3 a 1:
3 4 1
17
Busca em Grafos
Um algoritmo de busca (ou varredura) um algoritmo que examina, sistematicamente, todos os vrtices e todas as arestas de um grafo.
Cada aresta examinado uma s vez. Depois de visitar a ponta inicial de uma aresta, o algoritmo percorre aresta e visita sua ponta final.
Para justificar a palavra "busca", devemos imaginar que o algoritmo percorre o grafo buscando todos os vrtices que so acessveis a partir de um determinado vrtice em questo.
18
Busca em Grafos
H muitas maneiras de fazer uma tal busca. Cada estratgia de busca caracterizada pela ordem em que os vrtices so visitados.
Assim, a ordem de visita torna-se essencial se desejamos determinar outras propriedades alm da mera caracterstica de um determinado vrtice ser alcanado a partir de outro.
19
Busca em Grafos
O algoritmo de busca em grafos pode ento nos mostrar outras caractersticas de grafos.
Os algoritmos mais comumente discutidos so os algoritmos de busca em largura e de busca em profundidade, que sero apresentados a seguir
20
Busca em Largura
No algoritmo de busca em largura, a lista de vrtices obedece a poltica FIFO (First-In-First-Out, ou o primeiro a entrar ser o primeiro a sair Fila): o vrtice que sai da lista sempre o que est l h mais tempo.
O algoritmo pinta de preto todos os vrtices que podem ser alcanados a partir de um vrtice de origem at alcanar o vrtice de destino.
A principal caracterstica desse algoritmo que a busca segue um modelo de parametrizao pela distncia a partir da origem. No exemplo a seguir, vamos supor que estejamos buscando o caminho entre 1 e 5.
21
Exemplo: Busca em Largura
No incio todos os vrtices so pintados de branco. Para o exemplo o vrtice de origem o 1, sendo marcado com largura igual a zero. O algoritmo pinta de cinza este vrtice e o coloca em uma fila Q, mapeando tambm seus vizinhos. Neste caso, ele se conecta apenas com o vrtice 2.
Q = 1
22
Exemplo: Busca em Largura
No prximo passo, o vrtice 1 retirado da fila Q e pintado de preto, enquanto o vrtice 2 mapeado com largura igual a 1 e inserido na fila Q. O vrtice 2 ento pintado de cinza e seus vizinhos so mapeados. No caso, os vrtices 1, 3 e 5.
Q = 2
23
Exemplo: Busca em Largura
O vrtice 2 retirado da fila Q e pintado de preto, enquanto os vrtices 3 e 5 so colocados na fila Q e mapeados com largura igual a 2. O vrtice 1 no colocado na fila (apesar de haver uma conexo), pois j est pintado de preto.
Q = 3, 5
24
Exemplo: Busca em Largura
O vrtice 3 retirado da fila Q e pintado de preto, enquanto o vrtice 4 colocado na fila Q e mapeado com largura igual a 3.
Q = 5, 4
25
Exemplo: Busca em Largura
Em seguida o vrtice 5 tambm visitado, pintado de preto e retirado da fila Q. Como sua nica conexo com o vrtice 2 (j pintado de preto), nada feito.
Q = 4
26
Exemplo: Busca em Largura
No trmino da execuo deste exemplo o vrtice 4 pintado de preto e retirado da fila Q. Como suas conexes levam a vrtices j pintados de preto (1 e 5), nada feito e a fila torna-se vazia (fim do algoritmo).
Q vazia
27
Exemplo: Busca em Largura
Para o caminho entre origem e destino parte-se do vrtice de destino, examinado seus predecessores at chegar origem. Depois inverte-se o vetor conseguido. Para este exemplo, o caminho 1 25. A seguir apresentado um pseudocdigo do algoritmo de busca em largura.
Q vazia
28
Pseudocdigo: Busca em LarguraBusca_largura(Adj,origem,destino) // Adj a lista de adjacncias do grafo
t = tamanho de Adj;
para u = 1 at t,
cor(u) = branco;
fim
cor(origem) = cinza;
fila(1) = origem; i = 1; f = 2;
enquanto i < f,
u = fila(i); i = i + 1; c = Adj{u};
se (c no vazio),
para v = 1 at tamanho de c,
se cor(c(v)) == branco,
cor(c(v)) = cinza;
predecessor(c(v)) = u;
fila(f) = c(v); f = f + 1;
fim
cor(u) = preto;
fim
fim
fim
caminho(1) = destino; prev = predecessor(destino);
enquanto (prev ~= origem),
caminho(tamanho do caminho + 1) = prev; destino = prev;
prev = predecessor(destino);
fim
caminho(tamanho do caminho + 1) = prev;
para i = 1 at tamanho de caminho
caminho2(i) = caminho(tamanho do caminho-i+1);
fim
29
Busca em Profundidade
A estratgia seguida pela busca em profundidade , como seu nome implica, procurar cada vez mais fundo no grafo.
Nessa busca as arestas so exploradas a partir do vrtice v mais recentemente descoberto que ainda possui arestas inexploradas saindo dele.
Quando todas as arestas alcanadas a partir do vrtice de origem so visitadas a busca regressa para explorar as arestas que deixam o vrtice do qual v foi descoberto. Para o exemplo a seguir, tentaremos descobrir o caminho de 1 a 5.
30
Exemplo: Busca em Profundidade
No incio todos os vrtices so brancos, mas partindo do vrtice 1, este pintado de cinza e sua aresta examinada, levando ao vrtice 2. O vrtice 1 marcado com distncia 0.
31
Exemplo: Busca em Profundidade
O vrtice 1 pintado de preto. O vrtice 2 pintado de cinza, enquanto suas arestas sero examinadas e atribudo a ele uma distncia 1. A primeira aresta de 2 leva ao vrtice 1, j pintado de preto. Partindo para a segunda aresta, esta leva ao vrtice 3.
32
Exemplo: Busca em Profundidade
O vrtice 3 ento pintado de cinza e a ele atribudo uma distncia 2. Sua nica aresta examinada, levando ao vrtice 4.
33
Exemplo: Busca em Profundidade
O vrtice 3 pintado de preto e o vrtice 4 pintado de cinza, sendo que a ele atribudo uma distncia 3. Suas arestas sero examinadas. A primeira leva a um n j pintado de preto, logo no analisada. A segunda, leva ao vrtice 5.
34
Exemplo: Busca em Profundidade
O vrtice 4 pintado de preto e o vrtice 5 pintado de cinza, sendo que a ele atribudo uma distncia 4. Sua aresta examinada, constatando-se que leva a um vrtice j pintado de cinza.
35
Exemplo: Busca em Profundidade
O vrtice 5 pintado de preto e parte-se para o exame da ltima aresta pertencente ao vrtice 2.
36
Exemplo: Busca em Profundidade
Como neste momento esta aresta remete a um vrtice j pintado de preto (vrtice 5), o vrtice 2 tambm pintado de preto e o algoritmo terminado. Diferente da busca em largura, este algoritmo produz um caminho 1 2 3 4 5 para o caminho de 1 a 5.
37
Busca em Profundidade: Detalhes
O algoritmo de busca em profundidade na sua forma mais robusta utiliza um recurso computacional chamado recurso, em que uma dada funo chama a si mesma.
Um pseudocdigo para o algoritmo de busca em largura que encontra o caminho entre dois vrtices mostrado a seguir.
Claramente h uma grande diferena no modo de implementao e nos resultados dos dois algoritmos. Desta forma, quando h a necessidade de obteno do caminho mnimo entre dois vrtices, outros algoritmos podem ser utilizados.
38
Pseudocdigo: Busca em ProfundidadeBusca_profundidade(Adj,origem,destino) //Adj a lista de adjacncias do grafo
t = tamanho de Adj;
para u = 1 at t,
cor(u) = branco;
fim
caminho(1) = origem;
c = busca_em_prof(Adj,origem,destino,caminho);
funo busca_em_prof(Adj,u,d,caminho)
cor(u) = cinza;
v = Adj[u];
caminho2 = caminho;
se (v no vazio),
para i = 1 at tamanho(v),
se (caminho(tamanho(caminho))) != d),
se (v(i) igual a d),
cor(v(i)) = preto;
caminho = caminho2;
caminmho(tamanho(caminho2)+1) = d;
Salto;
seno se (cor(v(i)) == branco),
caminho = caminho2;
caminho(tamanho(caminho2)+1) = v(i);
c = busca_em_prof(Adj,v(i),d,caminho);
caminho = c;
fim
fim
fim
cor(u) = preto;
fim
39
Distncia
Um caminho C num grafo mnimo se no existe outro caminho com mesma origem e mesmo trmino que C mas comprimento menor que o de C.
A distncia de um vrtice s a um vrtice t num grafo o comprimento de um caminho mnimo de s a t. Se no existe caminho algum de s a t, a distncia de s a t infinita.
A distncia de s a t d se e somente se (1) existe um caminho de comprimento d de s a t e (2) nenhum caminho de s a t tem comprimento menor que d.
Em geral, num grafo direcionado a distncia de um vrtice s a um vrtice t diferente da distncia de t a s. Se o grafo no-orientado, entretanto, as duas distncias so iguais.
40
Grafos Ponderados
Muitas aplicaes associam um nmero a cada aresta de um grafo. Diremos que esse nmero o custo da aresta, que pode ser remetido a uma caracterstica fsica da conexo.
Por exemplo, se duas arestas de um grafo representam conexes de cabos ticos entre cidades A, B, e C (vrtices do grafo), sendo que a distncia entre A e B o dobro da distncia de A a C, ento pode-se atribuir um custo maior aresta que liga os vrtices A e B.
Dependendo da aplicao, pode ser mais apropriado dizer "peso" ou "comprimento" no lugar de "custo".
41
Exemplo: Caminho de Custo Mnimo
Se o grafo ponderado e direcionado abaixo for tomado como exemplo, o caminho mnimo C de 1 a 5 tem custo d igual a 2, levando a um caminho 1 2 5.
Perceba que existe um outro caminho 1 2 3 4 5, mas este possui custo d igual a 5.
Parte 2: Algoritmos de Caminhos Mnimos
43
Busca de Caminhos Mnimos
Para a busca de caminhos mnimos em grafos h algoritmos especficos que executam a tarefa.
Entretanto h formas especficas para tratar o problema, sendo diferentes quando busca-se caminhos mnimos a partir de um dado vrtice ou quando se buscam os caminhos mnimos entre todos os pares de vrtices.
44
Caminho Mnimo com Origem Fixa
Problema dos Caminhos Mnimos com Origem Fixa: dado um vrtice s de um grafo com custos nos arcos, encontrar, para cada vrtice t que pode ser alcanado a partir de s, um caminho mnimo simples de sa t. Todos os algoritmos para esses problemas exploram a seguinte propriedade bsica:
Propriedade Triangular: Para quaisquer vrtices x, y e z de um grafo com custos no-negativos nos arcos, tem-se
d(x,z) d(x,y) + d(y,z) , sendo d(i,j) a distncia de i a j.
45
Algoritmo de Dijkstra
Um algoritmo eficiente para a obteno do caminho mnimo em grafos com custos no-negativos o chamado algoritmo de Dijkstra.
O algoritmo pode ser usado, em particular, para encontrar um caminho de custo mnimo de um dado vrtice a outro, ou a todos os outros vrtices.
O algoritmo de Dijkstra funciona de forma iterativa, passo a passo, como mostrado a seguir. A entrada a matriz de adjacncias do grafo.
46
Algoritmo de Dijkstra
1. Como primeiro passo atribuda uma distncia para todos os pares de vrtices. De incio atribuda uma distncia infinita para todos, menos para o vrtice de origem.
2. Marque todos os vrtices como no visitados e defina o vrtice inicial como vrtice corrente.
3. Para este vrtice corrente, considere todos os seus vrtices vizinhos no visitados e calcule a distncia a partir do vrtice. Se a distncia for menor do que a definida anteriormente, substitua a distncia.
4. Quando todos os visinhos do vrtice corrente forem visitados, marque-o como visitado, o que far com que ele no seja mais analisado (sua distncia mnima e final).
5. Eleja o vrtice no visitado com a menor distncia (a partir do vrtice inicial) como o vrtice corrente e continue a partir do passo 3.
47
Exemplo: Algoritmo de Dijkstra
Para o exemplo a seguir, o vrtice 1 o vrtice origem e o vrtice corrente do incio do algoritmo. A distncia dele para todos os outros vrtices mostrada em vermelho. A distncia para seu vizinho (vrtice 2) igual a 1.
D = 1
D =
D =
D =
D = 0
48
Exemplo: Algoritmo de Dijkstra
O vrtice 2 passa a ser o vrtice corrente. A partir dele, atinge-se os vrtices 3 e 5, sendo as respectivas distncias calculadas para 2 (ao invs de infinito) e 2.
D = 1D = 2
D = 2
D =
D = 0
D = 1
49
Exemplo: Algoritmo de Dijkstra
O vrtice 3 o vrtice corrente. A partir dele alcana-se o vrtice 4, com distncia 4. Neste ponto todos os vrtices foram visitados e o vetor de distncias mnimas a partir do vrtice 1 D = [0 1 2 4 2].
D = 1D = 2
D = 2
D = 4
D = 0
D = 2
50
Pseudocdigo: Algoritmo de Dijkstra
Dijkstra(grafo,origem)
para cada vrtice v em grafo
distancia[v] = Infinito;
predecessor[v] = -1;
fim
distancia[origem] = 0;
Q = todos os vrtices de grafo;
enquanto (Q no vazio) faa,
u = vrtice grafo com menor distncia;
se (distancia[u] == Infinito)
Salta o lao;
fim
remova u de Q;
para cada vizinho v de u
d = distancia[u] + distancia entre u e v;
se (d < distancia[v]),
distancia[v] = d;
predecessor[v] = u;
fim
fim
fim
fim
51
Caminhos mnimos entre todos os pares de vrtices
O Algoritmo de Floyd-Warshall um algoritmo muito eficiente para encontrar todos as distncias mnimas dos pares de caminhos em um grafo.
Em aplicaes onde necessria a criao de uma matriz de caminhos mnimos ao invs de um vetor, este algoritmo mais aconselhvel.
52
Algoritmo de Floid-Warshall
O algoritmo de Floyd-Warshall deve primeiramente modificar a matriz de adjacncia do grafo, de modo que todas as posies dos pares de vrtices em que no houver conexes sejam setadas como Infinito.
Um pseudocdigo da implementao mostrado a seguir, sendo a entrada do programa a prpria matriz de adjacncias. O programa retorna uma matriz com todos os pares de caminhos mnimos.
53
Pseudocdigo: Algoritmo de Floyd-Warshall
FloidWarshall(Madj)
para cada linha i em Madj
para cada coluna j em Madj
se (Madf[i][j] == 0)
Madj[i][j] == Infinito;
fim
fim
fim
t = numero de linhas de Madj;
Cmin = Madj;
para k igual a 1 at t,
para i igual a 1 at t,
para j igual a 1 at t,
Cmin[i][j] = min(Cmin[i][j],Cmin[i][k]+Cmin[k][j]);
fim
fim
fim
retorna Cmin;
fim
54
Referncias Bibliogrficas
T. H. Cormen, C. H. Leiserson, R. L. Rivest, C. Stein, Algoritmos: Teoria e Prtica, Editora Campus, 2002.
R. Sedgewick, Algorithms in C, Addison Wisley, 1990.
http://www.ime.usp.br/~pf/algoritmos_para_grafos/
http://www.ime.usp.br/~pf/analise_de_algoritmos/lectures.html
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
http://www.algorithmist.com/index.php/Floyd-Warshall%27s_Algorithm
55
Exerccios Propostos
1. Um grafo no-ponderado representado pela lista de adjacncias Adj = {[2]; [3]; [4,5,8]; []; [6,7]; [1]; [9]; [10]; [10]; []}. Represente graficamente este grafo e aplique o algoritmo de busca em largura e busca em profundidade para encontrar o caminho entre os vrtices 1 e 10.
2. Considere um grafo orientado e ponderado que seja representado pela matriz de adjacncia abaixo. Simule o algoritmo de Dijkstra e determine o vetor de distncias a partir do vrtice 1. Faa grficos para mostrar a evoluo do algoritmo.
3. Usando a mesma matriz de adjacncias do exerccio anterior, implemente o algoritmo de Floid-Warshall em qualquer linguagem para calcular a matriz de caminhos mnimos.
56
Atividade extra
Uma rede de informao possui uma topologia representada por um grafo cuja matriz de adjacncias dada a seguir.
Aps um certo tempo de operao t o roteador representado pelo vrtice 2 cai, deixando de existir as conexes que chegam e saem deste vrtice. Passado um tempo t aps a queda do vrtice 2 o vrtice 6 tambm cai e aps 2t a vez do vrtice 12 sair de operao. Utilizando recursos computacionais, faa uma anlise dos custos representados para o escoamento de informao devido inoperabilidade destes roteadores e justifique suas afirmaes por meio de grficos e tabelas. Qual destas falhas representa a principal falha individual?