Grafos
 Grafo G = (V, E)
•
V — conjunto de vértices
•
E — conjunto de arestas (ou arcos)
- cada aresta é um par de vértices (v, w), em que v, w  V
- se o par for ordenado, o grafo é dirigido, ou digrafo
- um vértice w é adjacente a um vértice v se e só se (v, w)  E
- num grafo não dirigido com aresta (v, w) e, logo, (w, v) w é adjacente a v e v adjacente a w
- as arestas têm por vezes associado um custo ou peso
1
3
2
5
4
6
1
7
G1= (Cruzamentos, Ruas)
3
2
5
4
6
7
G2 = (Cidades, Estradas)
Grafos - 1
Mais definições
 caminho — sequência de vértices v1, v2, …, vn tais que (vi, vi+1)  E, 1 i <n
• comprimento do caminho é o número de arestas, n-1
- se n = 1, o caminho reduz-se a um vértice v1; comprimento = 0
• anel — caminho v, v  (v, v)  E , comprimento 1; raro
•
caminho simples — todos os vértices distintos excepto possivelmente o primeiro e o
último
 ciclo — caminho de comprimento  1 com v1 = vn
• num grafo não dirigido requer-se que as arestas sejam diferentes
• DAG — grafo dirigido acíclico
 conectividade
• grafo não dirigido é conexo sse houver um caminho a ligar qualquer par de vértices
• digrafo com a mesma propriedade — fortemente conexo
• digrafo fracamente conexo — não fortemente conexo; grafo subjacente conexo
 densidade
• grafo completo — existe uma aresta entre qualquer par de nós
• grafo denso — |E| = Q(V2)
•
grafo esparso — |E| = Q(V)
Grafos - 2
Representação
 matriz de adjacências
•
•
•
•
1
2
3
4
5
6
7
1
0
1
1
1
0
0
0
2
0
0
0
1
1
0
0
3
0
0
0
0
0
1
0
4
0
0
1
0
0
1
1
5
0
0
0
1
0
0
1
6
0
0
0
0
0
0
0
7
0
0
0
0
0
1
0
a[u][v] = 1 sse (u, v)  E
elementos da matriz podem ser os pesos (sentinelas indicam não aresta)
apropriada para grafos densos
3000 cruzamentos e 12 000 troços de ruas (4 por cruzamento)
- 9 000 000 de elementos na matriz!
Grafos - 3
Lista de adjacências
 estrutura típica para grafos esparsos
• para cada vértice, mantém-se a lista dos vértices adjacentes
• vector de cabeças de lista, indexado pelos vértices
• espaço é O(|E| + |V|)
• pesquisa dos adjacentes em tempo proporcional ao número destes
 grafo não dirigido: matriz simétrica; lista com o dobro do espaço
1
2
4
2
4
5
3
6
4
6
7
5
4
7
3
3
6
7
6
Grafos - 4
Arestas
class Edge
{
public Vertex
public double
dest; // Second vertex in Edge
cost; // Edge cost
public Edge( Vertex d, double c )
{
dest = d;
cost = c;
}
}
Grafos - 5
Vértices
class Vertex
{
public String name; // Vertex name
public List
adj; // Adjacent vertices
public double dist; // Cost
public Vertex prev; // Previous vertex on shortest path
public int
scratch;// Extra variable used in algorithm
public Vertex( String nm )
{ name = nm; adj = new LinkedList( ); reset( ); }
public void reset( )
{ dist = Graph.INFINITY; prev = null; pos = null; scratch = 0; }
public PriorityQueue.Position pos; // Used for dijkstra2 (Chapter 23)
}
Grafos - 6
Ordenação topológica
Ordenação dos vértices de um DAG tal que, se existe
um caminho de v para w, então v aparece antes de w
•
impossível se o grafo for cíclico
•
não é necessariamente única
(1 2 5 4 3 7 6) ou (1 2 5 4 7 3 6) no exemplo anterior
 algoritmo simples:
- descobrir um vértice sem arestas de chegada
- imprimir o vértice
- eliminá-lo e às arestas que dele saem
- repetir o processo no grafo restante
•
Indegree(v) — é o número de arestas (w, v)
•
passagem sequencial do vector é O(|V|); com |V| chamadas: tempo é O( |V|2 )
Grafos - 7
Versão ineficiente
void topsort()throws CycleFound
{
Vertex v, w;
for(int conta = 0; conta <= NUM_VERTEX; conta ++)
{
v = novo_Vertice_Indegree_Zero();
if( v == null )
throw new CycleFound();
v.topNum = conta;
for each w adjacent to v
w.indegree--;
}
}
Grafos - 8
Refinamento da ordenação topológica
 melhoria: em cada iteração, colocar numa fila (ou pilha) os vértices com indegree=0
•
em cada passo, é retirado da fila um qualquer dos vértices presentes
•
ao actualizar o indegree na lista de adjacências do vértice a eliminar colocamse na fila os que passam a ter indegree=0
•
inicialização põe na fila os vértices com indegree=0 à partida
•
tempo de execução O(|E| + |V|)
- o corpo do ciclo de actualização do indegree é executado no máximo uma
vez por aresta
- as operações na fila são executadas no máximo uma vez por vértice
- a inicialização leva um tempo proporcional ao tamanho do grafo
Grafos - 9
Algoritmo refinado
void topsort ()throws CycleFound
{
int counter = 0;
Vertex v, w;
Queue q;
q= new Queue();
for each vertex v
if ( v.indegree == 0 )
q.enqueue( v );
while( !q.isEmpty() )
{
v = q.dequeue();
v.topNum = ++counter;
for each w adjacent to v
if( --w.indegree == 0 )
q.enqueue( w );
}
if( counter != NUM_VERTEX )
throw new CycleFound();
}
Grafos - 10
Execução no grafo de exemplo
indegree anterior a cada operação dequeue
Vértice
1
2
3
4
5
6
7
v1
0
0
0
0
0
0
0
v2
1
0
0
0
0
0
0
v3
2
1
1
1
0
0
0
v4
3
2
1
0
0
0
0
v5
1
1
0
0
0
0
0
v6
3
3
3
3
2
1
0
v7
2
2
2
1
0
0
0
enqueue
v1
v2
v5
v4
v3,v7
dequeue
v1
v2
v5
v4
v3
v6
v7
v6
Grafos - 11
Caminho mais curto
Dado um grafo pesado G = (V, E) e um vértice s, obter o caminho
pesado mais curto de s para cada um dos outros vértices em G
 Exemplo: rede de computadores, com custo de comunicação e de atraso dependente do
encaminhamento (o caminho mais curto de v7 para v6 tem custo 1)
•
arestas com custo negativo complicam o problema
•
ciclos com custo negativo tornam o caminho mais curto indefinido (de v4 a v7 o
custo pode ser 2 ou -1 ou -7 ou …)
 Outro exemplo: se o grafo representar ligações aéreas, o problema típico poderá ser: Dado
um aeroporto de partida obter o caminho mais curto para um destino
•
não há algoritmo que seja mais eficiente
a resolver este problema do que a resolver
o mais geral
4
2
1
1
5
3
2
-10
3
1
4
6
6
2
2
1
7
5
6
Grafos - 12
1 - Caminho não pesado
 pretende-se o comprimento dos caminhos: pode ser visto como um caso
particular em que o peso de cada aresta é unitário
•
começa-se por marcar o vértice inicial s com comprimento 0
•
sucessivamente, passa-se aos que lhe estão adjacentes e marcam-se com
mais 1 do que o valor do caminho até ao antecedente
•
progride-se por níveis, passando ao nível seguinte só depois de ter
esgotado o anterior
 este tipo de pesquisa em grafos designa-se por pesquisa em largura
•
semelhante à travessia por níveis de uma árvore
 código usa uma tabela em que regista, para cada vértice v
- a distância de cada vértice ao inicial (dist)
- se o vértice já foi processado (known)
- qual o antecessor no caminho mais curto (path)
Grafos - 13
Evolução da marcação do grafo
1
v1
v2
v1
0
v2
0
v3
v4
v6
v5
v3
v7
v4
v6
v5
v7
1
1
1
v1
v2
2
v1
0
v2
2
0
v3
v4
v6
2
v7
1
v5
v3
v4
v6
2
v7
1
v5
3
3
Grafos - 14
Algoritmo básico
void unweighted( Vertex s)
{
Vertex v, w;
s.dist = 0;
for(int currDist = 0; currDist < NUM_VERTEX; currDist++)
for each vertex v
if( !v.known && v.dist == currDist )
{
v.known = true;
for each w adjacent to v
if( w.dist == INFINITY )
{
w.dist = currDist + 1;
w.path = v;
}
}
}
Grafos - 15
Eficiência do algoritmo básico
 tempo de execução O(|V|^2), devido aos ciclos for encaixados
 remoção da ineficiência semelhante à da ordenação topológica
•
em cada momento, só existem dois tipos de vértices não processados com
Dist  
- os do nível corrente (dist = currDist) ainda não processados e os
adjacentes a estes já marcados no nível seguinte
(dist=currDist+1)
•
podiam guardar-se em duas caixas diferentes mas, como só se marca o
primeiro do nível seguinte depois de ter todos os do nível corrente, basta
usar uma fila
•
o atributo known não é usado nesta solução
Grafos - 16
Algoritmo refinado
void unweighted( Vertex s)
{
Vertex v, w;
Queue q;
 tempo de execução é O(|E| + |V|), com grafo
representado por lista de adjacências
q= new Queue();
q.enqueue (s); s.dist = 0;
while( !q.isEmpty() )
{
v = q.dequeue();
v.known = true;
//agora desnecessário
for each w adjacent to v
if( w.dist == INFINITY )
{
w.dist = v.dist + 1;
w.path = v;
q.enqueue( w );
}
}}
Grafos - 17
Evolução da estrutura de dados
Início
Visita v3
Visita v1
Visita v6
v
known
v1
0

0
0
1
v3
1
1
v3
1
1
v3
v2
0

0
0

0
0
2
v1
0
2
v1
v3
0
0
0
1
0
0
1
0
0
1
0
0
v4
0

0
0

0
0
2
v1
0
2
v1
v5
0

0
0

0
0

0
0

0
v6
0

0
0
1
v3
0
1
v3
1
1
v3
v7
0

0
0

0
0

0
0

0
Q
dv
v3
pv
known
dv
v1, v6
pv
known
dv
pv
v6, v2, v4
known
dv
pv
v2, v4
Grafos - 18
Evolução da estrutura de dados
v
Visita v2
Known
dv
pv
Visita v4
Known
dv
pv
Visita v5
Known
dv
pv
Visita v7
Known
dv
pv
v1
1
1
v3
1
1
v3
1
1
v3
1
1
v3
v2
1
2
v1
1
2
v1
1
2
v1
1
2
v1
v3
1
0
0
1
0
0
1
0
0
1
0
0
v4
0
2
v1
1
2
v1
1
2
v1
1
2
v1
v5
0
3
v2
0
3
v2
1
3
v2
1
3
v2
v6
1
1
v3
1
1
v3
1
1
v3
1
1
v3
v7
0

0
0
3
v4
0
3
v4
0
3
v4
Q
v4, v5
v5, v7
v7
(vazia)
Grafos - 19
2 - Caminho pesado
 a solução é uma modificação da anterior
•
cada vértice mantém uma distância ao inicial, obtida somando pesos nos caminhos
•
quando se declara um vértice known , exploram-se os seus adjacentes; se o
caminho através deste nó é melhor que o já registado, modifica-se este
•
distância corrente em cada vértice: a melhor usando apenas vértices já processados
•
o ponto crucial: escolher para declarar known o vértice que tiver o menor custo até
ao momento
•
é o único cujo custo não pode diminuir
•
todas as melhorias de caminhos que usam este vértice são exploradas
 este é um exemplo de um algoritmo ganancioso: em cada passo faz o que melhora o
ganho imediato
 restrição: só é válido se não existirem custos negativos
 regista-se o vértice antecedente, responsável directo pelo custo estimado; seguindo a
sequência recupera-se o caminho mínimo
Grafos - 20
Evolução do algoritmo de Dijkstra
0
2
2
v1
4
v2
1
10
3
3
1
2
v3
3
v4
v5
2
8
5
4
9 8,
9,
8 6
v6
1
5
6
v7
Grafos - 21
Estádios do algoritmo de Dijkstra
4
2
v1
v2
1
10
4
2
v1
v2
1
10
3
v3
2
v4
8
5
4
3
2
4
v6
v7
1
2
v1
v5
2
v4
8
6
v2
1
v3
10
5
4
2
4
v6
v7
1
2
v1
2
v4
8
5
v6
1
10
3
2
4
1
6
v2
3
v3
v5
v7
v5
v3
2
v4
8
6
5
v6
2
4
1
v7
v5
6
Grafos - 22
Estádios do algoritmo de Dijkstra
4
2
v1
v2
1
10
4
2
v1
v2
1
10
3
v3
2
v4
8
5
4
3
2
4
v6
v7
1
2
v1
v5
2
v4
8
6
v2
1
v3
10
5
4
2
4
v6
v7
1
2
v1
2
v4
8
5
v6
1
10
3
2
4
1
6
v2
3
v3
v5
v7
v5
v3
2
v4
8
6
5
v6
2
4
1
v7
v5
6
Grafos - 23
Evolução da estrutura de dados
Início
Visita v1
Visita v4
Visita v2
v
known
v1
0
0
0
1
0
0
1
0
0
1
0
0
v2
0

0
0
2
v1
0
2
v1
1
2
v1
v3
0

0
0

0
0
3
v4
0
3
v4
v4
0

0
0
1
v1
1
1
v1
1
1
v1
v5
0

0
0

0
0
3
v4
0
3
v4
v6
0

0
0

0
0
9
v4
0
9
v4
v7
0

0
0

0
0
5
v4
0
5
v4
dv
pv
known
dv
pv
known
dv
pv
known
dv
pv
Grafos - 24
Evolução da estrutura de dados
Visita v5
Visita v3
Visita v7
Visita v6
v
known
v1
1
0
0
1
0
0
1
0
0
1
0
0
v2
1
2
v1
1
2
v1
1
2
v1
1
2
v1
v3
0
3
v4
1
3
v4
1
3
v4
1
3
v4
v4
1
1
v1
1
1
v1
1
1
v1
1
1
v1
v5
1
3
v4
1
3
v4
1
3
v4
1
3
v4
v6
0
9
v4
0
8
v3
0
6
v7
1
6
v7
v7
0
5
v4
0
5
v4
1
5
v4
1
5
v4
dv
pv
known
dv
pv
known
dv
pv
known
dv
pv
Grafos - 25
Algoritmo de Dijkstra
void Dijkstra( Vertex s)
{
Vertex v, w;
s.dist
for( ;
{
v =
if(
= 0;
; )
vertice_a_menor_distancia;
v == null )
break;
v.known = true;
for each w adjacent to v
if( !w.known )
if v.dist + c(v,w) < w.dist )
{
w.dist = v.dist + c(v,w);
w.path = v;
}
}}
Grafos - 26
Análise do algoritmo
 problema: pesquisa do mínimo
•
método de percorrer a tabela até encontrar o mínimo é O(|V|) em cada fase; gastase O(|V|2) tempo ao longo do processo
•
tempo de corrigir a distância é constante por actualização e há no máximo uma
por aresta, num total de O(|E|)
•
tempo de execução fica O(|E| + |V|2) = O(|V|2)
•
se o grafo for denso |E| = Q(|V|2) e o resultado é satisfatório pois corre em tempo
linear no número de arestas
•
se o grafo fôr esparso |E| = Q(|V|), o algoritmo é demasiado lento
 melhoria: manter as distâncias numa fila de prioridade para obter o mínimo
eficientemente O(log |V|), com uma operação deleteMin
•
como as distâncias vão sendo alteradas no processo e a operação de Busca é
ineficiente nas filas de prioridade, pode-se meter na fila mais do que um elemento
para o mesmo vértice, com distâncias diferentes, e ter o cuidado, ao apagar o
mínimo, de verificar se o vértice já está processado
Tempo de execução total: O(|E| log |V|)
O(|E| log |V|) actualização dos pesos com operação decreaseKey na fila
O(|V| log |V|) percorrer os vértices com operação deleteMin para cada
Grafos - 27
3 - Arestas com custos negativos
 Algoritmo de Dijkstra não funciona
•
custo ao longo de um caminho não é monótono
•
depois de se marcar um vértice como processado pode aparecer um caminho mais
longo mas com custo inferior
 Combinar os algoritmos para os caminhos pesado e sem peso
•
usar uma fila; colocar o vértice inicial
•
em cada passo
-
retirar um vértice v da fila
-
para cada vértice w adjacente a v tal que dist(w)  dist(v) + cost(v, w) 
actualizar dist(w), path(w) e colocar w na fila, se lá não estiver
-
manter uma indicação de presença na fila
Grafos - 28
Exemplo: custos negativos
Achar os caminhos
de menor custo a
começar em 1.
4
4
•
0
1
2
1
2
3
5
1
4
8
6
2
2
1
6
7
3
•
4
0
1
2
1
2
3
5
0
4
8
6
8
2
2
-2
1
7
1
4
-2
1
9
10
2
4
6
7
vértice 2 não
altera nada …
5
3
6
5
10
2
4
1
8
5
2
2
2
2
3
6
•
0
1
4
5
7
2
5
4
6
4
pretendido:
2
4
8
2
•
10
-2
10
-2
1
2
1
2
3
5
Dijkstra
2
1
5
6
2
seria necessário rever 4
e propagar as alterações;
piora o tempo …
4
Grafos - 29
Algoritmo com custo negativo
void weightedNegative( Vertex s)
•
{
Vertex v, w;
Queue q;
•
q = new Queue();
q.enqueue (s);
while( !q.isEmpty() )
{
v = q.dequeue();
for each w adjacent to v
if v.dist + c(v,w) < w.dist )
{
w.dist = v.dist + c(v,w);
w.path = v;
•
•
pode ser necessário
processar cada vértice mais
do que uma vez (max: |V|)
actualização pode ser
executada O(|E|.|V|),
usando listas de adjacência
ciclo de custo negativo 
algoritmo não termina
teste de terminação: algum
vértice sai da fila mais do
que |V|+1 vezes
if(w not in q) )
q.enqueue(w);
}
}
}
Grafos - 30
4 - Grafos acíclicos
 simplificação do algoritmo de Dijkstra
•
exigência de selecção, em cada passo, do vértice mínimo é dispensável
•
nova regra de selecção: usar a ordem topológica
•
um vértice processado jamais pode vir a ser alterado: não há ramos a entrar
•
não é necessária a fila de prioridade
•
ordenação topológica e actualização das distâncias combinadas numa só passagem
 aplicações em processos não reversíveis
•
não se pode regressar a um estado passado (certas reacções químicas)
•
deslocação entre dois pontos em esqui (sempre descendente)
 aplicações de Investigação Operacional
•
•
modelar sequências de actividades em projectos
grafos nó-actividade
- nós representam actividades e respectiva duração
- arcos representam precedência (um arco de v para w significa que a actividade
em w só pode ser iniciada após a conclusão da de v)  acíclico
Grafos - 31
Grafos Nó-Actividade
Nó: actividade e tempo associado
Arco: precedência
C(3)
A(3)
início
F(3)
D(2)
B(2)
G(2)
E(1)
Qual a duração total
mínima do projecto?
fim
H(1)
K(4)
Quais as actividades que podem ser atrasadas e
por quanto tempo
(sem aumentar a duração do projecto)?
Grafos - 32
Reformulação em Grafo Nó-Evento
Nó: evento - completar actividade
Arco: actividade
C/3
2
4
A/3
0
0
D/2
6’
1
0
6
0
3
E/1
5
7
0
0
B/2
7’
F/3
8’
G/2
0
10’
0
10
0
8
K/4
H/1
9
• reformulação introduz
nós e arcos extra para garantir precedências
Grafos - 33
Menor Tempo de Conclusão
• menor tempo de conclusão de uma actividade
 caminho mais comprido do evento inicial ao nó de conclusão da actividade
• problema (se grafo não fosse acíclico): ciclos de custo positivo
• adaptar algoritmo de caminho mais curto
• MTC(1) = 0
MTC(w) = max( MTC(v) + c(v,w) )
MTC : usar ordem topológica
(v, w)  E
3
6
C/3
2
4
A/3
0
0
3
6’
1
B/2
2
3
0
D/2
5
0
6
0
3
E/1
0
5
0
6
7’
5
8’
F/3
G/2
K/4
9
7
7
8
9
0
10’
0
7
10
H/1
10
0
9
Grafos - 34
Último Tempo de Conclusão
• último tempo de conclusão: mais tarde que uma actividade pode terminar sem
comprometer as que se lhe seguem
UTC : usar ordem topológica inversa
• UTC(n) = MTC(n)
UTC(v) = min( UTC(w) - c(v, w) )
(v, w)  E
valores calculados em tempo linear
mantendo listas de adjacentes e de
precedentes dos nós
3
6
C/3
2
4
0
6
9
A/3
F/3
3
6
0
7’
7
0
3
5
9
10
0
0
D/2
6
H/1
9
6’
6
1
10’
10
0
5
0
7
G/2
0
4
6
9
10
0
0
8’
8
7
2
3
B/2
0
7 K/4
9
E/1
9
3
5
4
5
9
Grafos - 35
Folgas nas actividades
• folga da actividade
folga(v,w) = UTC(w)-MTC(v)-c(v,w)
3
A/3/0
6
C/3/0
2
4
3
6
5
7’
6
5
0
3
1
6’
6
0
4
6
3
B/2/2
2
3
4
E/1/2
D/2/1
5
5
6
8’
F/3/0
G/2/2
7 K/4/2
9
7
9
9
7
10’
9
8
7
9
9
H/1/0
10
10
10
9
Caminho crítico: só actividades de folga nula (há pelo menos 1)
Grafos - 36