BC-0506: Comunicação e Redes
Algoritmos em Grafos
Santo André, 2Q2011
1
Parte 1: Algoritmos de Busca
Rediscutindo: Representações
em Grafos
Matriz de Adjacências
Matriz de Incidências
Lista de Adjacências
3
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).
4
Exemplo: Grafo não-orientado
e Matriz de Adjacência
5
Exemplo: Grafo orientado e
Matriz de Adjacência
6
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.
7
Exemplo: Matriz de Incidência
8
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.
9
Exemplo: Lista de Adjacências
Adj[1] = {2}
Adj[2] = {1,3,5}
Adj[3] = {4}
Adj[4] = {1,5}
Adj[5] = {2}
10
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.
11
Exemplo: Grafos Ponderados e
Não-Ponderados
Em grafos ponderados,
representa-se entre
parênteses o custo da
aresta.
Pode-se ainda representar
um grafo não-ponderado
ignorando os custos das
arestas. Em um grafo nãoponderado, todas as
arestas possuem custo
igual a 1.
12
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.
13
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.
14
Exemplo de Caminho
Para o exemplo a seguir (não-orientado e nãoponderado), 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
15
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
16
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.
17
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.
18
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
19
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.
20
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
21
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
22
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
23
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
24
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
25
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
26
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
27
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
28
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.
29
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.
30
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.
31
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.
32
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.
33
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.
34
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.
35
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.
36
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.
37
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
38
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ãoorientado, entretanto, as duas distâncias são iguais.
39
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".
40
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.
41
Parte 2: Algoritmos de
Caminhos Mínimos
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.
43
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, temse
d(x,z) ≤ d(x,y) + d(y,z) , sendo d(i,j) a distância de i a j.
44
Algoritmo de Dijkstra
Um algoritmo eficiente para a obtenção do
caminho mínimo em grafos com custos nãonegativos é 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.
45
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.
46
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=∞
D=1
D=∞
D=∞
D=0
47
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=1
D=2
D=∞
D=0
48
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=2
D=1
D=2
D=4
D=0
D=2
49
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
50
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.
51
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.
52
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
53
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
54
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.
55
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?
56