Comunicação e redes - Algoritmos em grafos

Prévia do material em texto

1
BC-0506: Comunicação e Redes
Algoritmos em Grafos
Santo André, 2Q2011
Parte 1: Algoritmos de Busca
3
Rediscutindo: Representações 
em Grafos
Matriz de Adjacências
Matriz de Incidências 
Lista de Adjacências
4
Matriz de Adjacências
A matriz de adjacências de um grafo tem colunas 
e linhas indexadas pelos vértices. Se A for a 
matriz de adjacências de índices i e j, A(i,j) = 1 
se os vértices i e j forem conectados por uma 
aresta e A(i,j) = 0 caso contrário. Em grafos não 
orientados a matriz de adjacências é sempre 
simétrica, ou seja, A(i,j) = A(j,i).
5
Exemplo: Grafo não-orientado 
e Matriz de Adjacência
6
Exemplo: Grafo orientado e 
Matriz de Adjacência
7
Matriz de Incidência
A Matriz de Incidência representa 
computacionalmente um grafo em que as linhas e 
colunas são vértices e arestas. Assim, dado um grafo 
com n vértices e m arestas, podemos representá-lo por 
uma matriz B n x m, guardando informações sobre a 
incidência de vértices em cada aresta. 
Para representar um grafo sem pesos nas arestas e 
não-orientado, basta que as entradas da matriz B 
contenham +1 se a aresta chega no vértice, -1 se a 
aresta parte do vértice e 0 caso a aresta não chegue 
nem parta no/do vértice.
8
Exemplo: Matriz de Incidência
9
Lista de Adjacências
O vetor de listas de adjacência de um grafo tem 
uma lista encadeada para cada um de seus 
vértices. A lista de cada vértice v contém todos 
os vértices vizinhos que se pode alcançar a partir 
de v. 
10
Exemplo: Lista de Adjacências
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 não-ponderado. 
Se todas as arestas apresentarem um mesmo 
peso (ou custo), diz-se que o grafo é não 
ponderado e considera-se todas as arestas com 
custo igual a 1.
O grafo será ponderado se diferentes arestas 
possuírem custos distintos. 
12
Exemplo: Grafos Ponderados e 
Não-Ponderados
Pode-se ainda representar 
um grafo não-ponderado 
ignorando os custos das 
arestas. Em um grafo não-
ponderado, todas as 
arestas possuem custo 
igual a 1.
Em grafos ponderados, 
representa-se entre 
parênteses o custo da 
aresta.
13
Caminhos em Grafos
Um caminho num grafo é uma sequência de 
vértices dotada da propriedade de que cada novo 
vértice é adjacente ao anterior.
A origem de um caminho é o primeiro vértice do 
caminho. O término é o último vértice. Diz-se que 
um caminho com origem s e término t vai de s a t. 
Dizemos que uma aresta v → w pertence a um 
caminho se o vértice w é o sucessor de v no 
caminho. Todas as arestas de um caminho apontam 
no mesmo sentido, de um vértice para o seu 
sucessor.
14
Caminhos em Grafos
Costuma-se diferenciar caminho de passeio em 
grafos. Assim, em um caminho de s a t, não pode 
haver nenhum vértice repetido, enquanto em um 
passeio isso pode acontecer.
O comprimento de um caminho é o número de 
termos da sequência menos um. Em outras 
palavras, é o número de arestas do caminho. 
Em grafos não-orientados, a existência de 
caminhos é uma propriedade simétrica: para 
quaisquer dois vértices 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 (não-orientado e não-
ponderado), o caminho 1 a 3 deve ser passando 
pelo vértice 2.
Caminho 1 a 3: 1 → 2 → 3
Caminho 3 a 1: 3 → 2 → 1
16
Exemplo de Caminho
Para grafos orientados (ponderados ou não) 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 
vértices 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 
vértices que são acessíveis a partir de um 
determinado vértice em questão.
18
Busca em Grafos
Há muitas maneiras de fazer uma tal 
busca. Cada estratégia de busca é caracterizada 
pela ordem em que os vértices são visitados.
Assim, a ordem de visita torna-se essencial se 
desejamos determinar outras propriedades além 
da mera característica de um determinado 
vértice ser alcançado a partir de outro.
19
Busca em Grafos
O algoritmo de busca em grafos pode então nos 
mostrar outras características de grafos.
Os algoritmos mais comumente discutidos são os 
algoritmos de busca em largura e de busca em 
profundidade, que serão apresentados a seguir
20
Busca em Largura
No algoritmo de busca em largura, a lista de vértices 
obedece a política FIFO (First-In-First-Out, ou o 
primeiro a entrar será o primeiro a sair – Fila): 
o vértice que sai da lista é sempre o que está lá há mais 
tempo. 
O algoritmo pinta de preto todos os vértices que podem 
ser alcançados a partir de um vértice de origem até 
alcançar o vértice de destino.
A principal característica desse algoritmo é que a busca 
segue um modelo de parametrização pela distância 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 início todos os vértices são pintados de branco. Para 
o exemplo o vértice de origem é o 1, sendo marcado com 
“largura” igual a zero. O algoritmo pinta de cinza este 
vértice e o coloca em uma fila Q, mapeando também seus 
vizinhos. Neste caso, ele se conecta apenas com o 
vértice 2. 
Q = 1
22
Exemplo: Busca em Largura
No próximo passo, o vértice 1 é retirado da fila Q e 
pintado de preto, enquanto o vértice 2 é mapeado com 
“largura” igual a 1 e inserido na fila Q. O vértice 2 é 
então pintado de cinza e seus vizinhos são mapeados. No 
caso, os vértices 1, 3 e 5. 
Q = 2
23
Exemplo: Busca em Largura
O vértice 2 é retirado da fila Q e pintado de preto, 
enquanto os vértices 3 e 5 são colocados na fila Q e 
mapeados com “largura” igual a 2. O vértice 1 não é 
colocado na fila (apesar de haver uma conexão), pois já 
está pintado de preto. 
Q = 3, 5
24
Exemplo: Busca em Largura
O vértice 3 é retirado da fila Q e pintado de preto, 
enquanto o vértice 4 é colocado na fila Q e mapeado com 
“largura” igual a 3. 
Q = 5, 4
25
Exemplo: Busca em Largura
Em seguida o vértice 5 também é visitado, pintado de 
preto e retirado da fila Q. Como sua única conexão é com 
o vértice 2 (já pintado de preto), nada é feito. 
Q = 4
26
Exemplo: Busca em Largura
No término da execução deste exemplo o vértice 4 é 
pintado de preto e retirado da fila Q. Como suas 
conexões levam a vértices 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 
vértice de destino, examinado seus predecessores até 
chegar à origem. Depois inverte-se o vetor conseguido. 
Para este exemplo, o caminho é 1 →2→5. A seguir é 
apresentado um pseudocódigo do algoritmo de busca em 
largura. 
Q vazia
28
Pseudocódigo: Busca em Largura
Busca_largura(Adj,origem,destino) // Adj é a lista de adjacências 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 não é 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 estratégia seguida pela busca em profundidade 
é, como seu nome implica, procurar cada vez mais 
fundo no grafo. 
Nessa busca as arestas são exploradas a partir 
do vértice v mais recentemente descoberto que 
ainda possui arestas inexploradas saindo dele.
Quando todas as arestas alcançadas a partir do 
vértice de origem são visitadas a busca regressa 
para explorar as arestas que deixam o vértice do 
qual v foi descoberto. Para o exemplo a seguir, 
tentaremos descobrir o caminho de 1 a 5.
30
Exemplo: Busca em 
Profundidade
No início todos os vértices são brancos, mas 
partindo do vértice 1, este é pintado de cinza e 
sua aresta é examinada, levando ao vértice 2. O 
vértice 1 é marcado com distância 0.
31
Exemplo: Busca em 
Profundidade
O vértice 1 é pintado de preto. O vértice 2 é pintado de 
cinza, enquanto suas arestas serão examinadas e é 
atribuído a ele uma distância 1. A primeira aresta de 2 
leva ao vértice 1, já pintado de preto. Partindo para a 
segunda aresta, esta leva ao vértice 3.
32
Exemplo: Busca em 
Profundidade
O vértice 3 é então pintado de cinza e a ele é atribuído 
uma distância 2. Sua única aresta é examinada, levando ao 
vértice 4.
33
Exemplo: Busca em 
Profundidade
O vértice 3 é pintado de preto e o vértice 4 é pintado de 
cinza, sendo que a ele é atribuído uma distância 3. Suas 
arestas serão examinadas. A primeira leva a um nó já 
pintado de preto, logo não é analisada. A segunda, leva ao 
vértice 5.
34
Exemplo: Busca em 
Profundidade
O vértice 4 é pintado de preto e o vértice 5 é pintado de 
cinza, sendo que a ele é atribuído uma distância 4. Sua 
aresta é examinada, constatando-se que leva a um vértice 
já pintado de cinza. 
35
Exemplo: Busca em 
Profundidade
O vértice 5 é pintado de preto e parte-se para o exame 
da última aresta pertencente ao vértice 2. 
36
Exemplo: Busca em 
Profundidade
Como neste momento esta aresta remete a um vértice já 
pintado de preto (vértice 5), o vértice 2 também é 
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 recursão, em que uma dada 
função “chama a si mesma”.
Um pseudocódigo para o algoritmo de busca em 
largura que encontra o caminho entre dois vértices 
é mostrado a seguir.
Claramente há uma grande diferença no modo de 
implementação e nos resultados dos dois 
algoritmos. Desta forma, quando há a necessidade 
de obtenção do caminho mínimo entre dois 
vértices, outros algoritmos podem ser utilizados.
38
Pseudocódigo: Busca em 
Profundidade
Busca_profundidade(Adj,origem,destino) //Adj é a lista de adjacências 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);
função busca_em_prof(Adj,u,d,caminho)
cor(u) = cinza;
v = Adj[u];
caminho2 = caminho;
se (v não é 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;
senão 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
Distância
Um caminho C num grafo é mínimo se não existe outro caminho 
com mesma origem e mesmo término que C mas comprimento 
menor que o de C.
A distância de um vértice s a um vértice t num grafo é o 
comprimento de um caminho mínimo de s a t. Se não existe 
caminho algum de s a t, a distância de s a t é infinita.
A distância 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 distância de um vértice s a um 
vértice t é diferente da distância de t a s. Se o grafo é não-
orientado, entretanto, as duas distâncias são iguais. 
40
Grafos Ponderados
Muitas aplicações associam um número a cada aresta de 
um grafo. Diremos que esse número é o custo da 
aresta, que pode ser remetido a uma característica 
física da conexão.
Por exemplo, se duas arestas de um grafo representam 
conexões de cabos óticos entre cidades A, B, e C 
(vértices do grafo), sendo que a distância entre A e B é 
o dobro da distância de A a C, então pode-se atribuir 
um custo maior à aresta que liga os vértices A e B.
Dependendo da aplicação, pode ser mais apropriado 
dizer "peso" ou "comprimento" no lugar de "custo".
41
Exemplo: Caminho de Custo 
Mínimo
Se o grafo ponderado e direcionado abaixo for 
tomado como exemplo, o caminho mínimo 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 Mínimos
43
Busca de Caminhos Mínimos
Para a busca de caminhos mínimos em grafos há 
algoritmos específicos que executam a tarefa.
Entretanto há formas específicas para tratar o 
problema, sendo diferentes quando busca-se 
caminhos mínimos a partir de um dado vértice ou 
quando se buscam os caminhos mínimos entre 
todos os pares de vértices.
44
Caminho Mínimo com Origem 
Fixa
Problema dos Caminhos Mínimos com Origem 
Fixa: dado um vértice s de um grafo com custos nos 
arcos, encontrar, para cada vértice t que pode ser 
alcançado a partir de s, um caminho mínimo simples de s
a t. Todos os algoritmos para esses problemas exploram 
a seguinte propriedade básica: 
Propriedade Triangular: Para quaisquer vértices x, y e 
z de um grafo com custos não-negativos nos arcos, tem-
se 
d(x,z) ≤ d(x,y) + d(y,z) , sendo d(i,j) a distância de i a j. 
45
Algoritmo de Dijkstra
Um algoritmo eficiente para a obtenção do 
caminho mínimo em grafos com custos não-
negativos é o chamado algoritmo de Dijkstra. 
O algoritmo pode ser usado, em particular, para 
encontrar um caminho de custo mínimo de um 
dado vértice a outro, ou a todos os outros 
vértices. 
O algoritmo de Dijkstra funciona de forma 
iterativa, passo a passo, como mostrado a 
seguir. A entrada é a matriz de adjacências do 
grafo.
46
Algoritmo de Dijkstra
1. Como primeiro passo é atribuída uma distância para todos os pares de 
vértices. De início é atribuída uma distância infinita para todos, menos 
para o vértice de origem.
2. Marque todos os vértices como não visitados e defina o vértice inicial 
como vértice corrente. 
3. Para este vértice corrente, considere todos os seus vértices vizinhos 
não visitados e calcule a distância a partir do vértice. Se a distância 
for menor do que a definida anteriormente, substitua a distância. 
4. Quando todos os visinhos do vértice corrente forem visitados, 
marque-o como visitado, o que fará com que ele não seja mais analisado 
(sua distância é mínima e final).
5. Eleja o vértice não visitado com a menor distância (a partir do vértice 
inicial) como o vértice corrente e continue a partir do passo 3.
47
Exemplo: Algoritmo de Dijkstra
Para o exemplo a seguir, o vértice 1 é o vértice 
origem e o vértice corrente do início do 
algoritmo. A distância dele para todos os outros 
vértices é mostrada em vermelho. A distância 
para seu vizinho (vértice 2) é igual a 1.
D = 1D = ∞
D = ∞
D = ∞
D = 0
48
Exemplo: Algoritmo de Dijkstra
O vértice 2 passa a ser o vértice corrente. A 
partir dele, atinge-se os vértices 3 e 5, sendo as 
respectivas distâncias calculadas para 2 (ao invés 
de infinito) e 2.
D = 1
D = 2
D = 2
D = ∞
D = 0
D = 1
49
Exemplo: Algoritmo de Dijkstra
O vértice 3 é o vértice corrente. A partir dele 
alcança-se o vértice 4, com distância 4. Neste 
ponto todos os vértices foram visitados e o vetor 
de distâncias mínimas a partir do vértice 1 é 
D = [0 1 2 4 2].
D = 1
D = 2
D = 2
D = 4
D = 0
D = 2
50
Pseudocódigo: Algoritmo de 
Dijkstra
Dijkstra(grafo,origem)
para cada vértice v em grafo
distancia[v] = Infinito;
predecessor[v] = -1;
fim
distancia[origem] = 0;
Q = todos os vértices de grafo;
enquanto (Q não é vazio) faça,
u = vértice é grafo com menor distância;
se (distancia[u] == Infinito)
Salta o laço;
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 mínimos entre todos 
os pares de vértices
O Algoritmo de Floyd-Warshall é um algoritmo 
muito eficiente para encontrar todos as 
distâncias mínimas dos pares de caminhos em um 
grafo. 
Em aplicações onde é necessária a criação de uma 
matriz de caminhos mínimos ao invés de um vetor, 
este algoritmo é mais aconselhável.
52
Algoritmo de Floid-Warshall
O algoritmo de Floyd-Warshall deve 
primeiramente modificar a matriz de adjacência 
do grafo, de modo que todas as posições dos 
pares de vértices em que não houver conexões 
sejam setadas como Infinito.
Um pseudocódigo da implementação é mostrado a 
seguir, sendo a entrada do programa a própria 
matriz de adjacências. O programa retorna uma 
matriz com todos os pares de caminhos mínimos.
53
Pseudocódigo: 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
Referências Bibliográficas
T. H. Cormen, C. H. Leiserson, R. L. Rivest, C. Stein, ”Algoritmos: Teoria e 
Prática”, 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
Exercícios Propostos
1. Um grafo não-ponderado é representado pela lista de adjacências 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 vértices 1 e 10. 
2. Considere um grafo orientado e ponderado que seja representado pela matriz de 
adjacência abaixo. Simule o algoritmo de Dijkstra e determine o vetor de distâncias a 
partir do vértice 1. Faça gráficos para mostrar a evolução do algoritmo.
3. Usando a mesma matriz de adjacências do exercício anterior, implemente o 
algoritmo de Floid-Warshall em qualquer linguagem para calcular a matriz de caminhos 
mínimos.
56
Atividade extra
Uma rede de informação possui uma topologia representada por um grafo cuja matriz de adjacências é dada a 
seguir.
Após um certo tempo de operação t o roteador representado pelo vértice 2 cai, deixando de existir as conexões 
que chegam e saem deste vértice. Passado um tempo t após a queda do vértice 2 o vértice 6 também cai e após 2t é 
a vez do vértice 12 sair de operação. Utilizando recursos computacionais, faça uma análise dos custos 
representados para o escoamento de informação devido à inoperabilidade destes roteadores e justifique suas 
afirmações por meio de gráficos e tabelas. Qual destas falhas representa a principal falha individual?