Post on 23-Aug-2020
Grafos 1
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 2
3 4 5
6 7
1 2
3 4 5
6 7
G1= (Cruzamentos, Ruas) G2 = (Cidades, Estradas)
Grafos 2
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, n1 se n = 1, o caminho reduzse 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 requerse 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| = Θ(V2)
• grafo esparso — |E| = Θ(V)
Grafos 3
Representação❏ matriz de adjacências
• 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!
1 2 3 4 5 6 71 0 1 1 1 0 0 02 0 0 0 1 1 0 03 0 0 0 0 0 1 04 0 0 1 0 0 1 15 0 0 0 1 0 0 16 0 0 0 0 0 0 07 0 0 0 0 0 1 0
Grafos 4
Lista de adjacências❏ estrutura típica para grafos esparsos
• para cada vértice, mantémse 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
21
2
3
4
5
6
7
34
54
6
6 37
74
6
Grafos 5
Ordenação topológica
• 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 )
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
Grafos 6
Versão ineficientevoid 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 7
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 8
Algoritmo refinado
void topsort ()throws CycleFound{
int counter = 0;Vertex v, w;Queue q;
q= new Queue();for each vertex vif ( v.indegree == 0 )
q.enqueue( v );
while( !q.isEmpty() ){
v = q.dequeue();v.topNum = ++counter;
for each w adjacent to vif( w.indegree == 0 )q.enqueue( w );
}if( counter != NUM_VERTEX )
throw new CycleFound(); }
Grafos 9
Execução no grafo de exemploindegree 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 v6
dequeue v1 v2 v5 v4 v3 v7 v6
Grafos 10
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
1 2
3 4 5
6 7
1
2
34
5
6
101
6
2
21
Grafos 11
1 Caminho não pesado
❏ pretendese o comprimento dos caminhos: pode ser visto como um caso particular em que o peso de cada aresta é unitário
• começase por marcar o vértice inicial s com comprimento 0• sucessivamente, passase aos que lhe estão adjacentes e marcamse com
mais 1 do que o valor do caminho até ao antecedente• progridese por níveis, passando ao nível seguinte só depois de ter
esgotado o anterior❏ este tipo de pesquisa em grafos designase 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 12
Evolução da marcação do grafo
v1 v2
v3 v4 v5
v6 v7
v1 v2
v3 v4 v5
v6 v7
v1 v2
v3 v4 v5
v6 v7
0 0
1
1
0
1
1
2
2 v1 v2
v3 v4 v5
v6 v7
0
1
1
2
2
3
3
Grafos 13
Algoritmo básicovoid unweighted( Vertex s){
Vertex v, w;
s.dist = 0;for(int currDist = 0; currDist < NUM_VERTEX; currDist++)
for each vertex vif( !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 14
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 guardarse 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 15
Algoritmo refinado
❏ tempo de execução é O(|E| + |V|), com grafo representado por lista de adjacências
void unweighted( Vertex s){
Vertex v, w;Queue q;
q= new Queue();q.enqueue (s); s.dist = 0;
while( !q.isEmpty() ){
v = q.dequeue();v.known = true; //agora desnecessáriofor each w adjacent to v
if( w.dist == INFINITY ){
w.dist = v.dist + 1;w.path = v;q.enqueue( w );
}}}
Grafos 16
Evolução da estrutura de dados
v
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 v3 v6, v2, v4 v2, v4v1, v6
Início Visita v3 Visita v1 Visita v6 known dv pv known dv pv known dv pv known dv pv
Grafos 17
Evolução da estrutura de dados
v
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 v7 (vazia)v5, v7
Visita v4 Visita v5 Visita v7 Known dv pv Known dv pv Known dv pv Known dv pv
v4, v5
Visita v2
Grafos 18
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 , exploramse os seus adjacentes; se o caminho através deste nó é melhor que o já registado, modificase 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
❏ registase o vértice antecedente, responsável directo pelo custo estimado; seguindo a sequência recuperase o caminho mínimo
Grafos 19
Estádios do algoritmo de Dijkstra
v1 v2
v3 v4 v5
v6 v7
42
10
6
1
5
13
24
8
2
v1 v2
v3 v4 v5
v6 v7
42
10
6
1
5
13
24
8
2
v1 v2
v3 v4 v5
v6 v7
42
10
6
1
5
13
24
8
2
v1 v2
v3 v4 v5
v6 v7
42
10
6
1
5
13
24
8
2
Grafos 20
Estádios do algoritmo de Dijkstra
v1 v2
v3 v4 v5
v6 v7
42
10
6
1
5
13
24
8
2
v1 v2
v3 v4 v5
v6 v7
42
10
6
1
5
13
24
8
2
v1 v2
v3 v4 v5
v6 v7
42
10
6
1
5
13
24
8
2
v1 v2
v3 v4 v5
v6 v7
42
10
6
1
5
13
24
8
2
Grafos 21
Evolução da estrutura de dados
v
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 ∞ 0 0 5 v4
Início Visita v1 Visita v4 Visita v2 known dv pv known dv pv known dv pv known dv pv
Grafos 22
Evolução da estrutura de dados
v
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
Visita v3 Visita v7 Visita v6 known dv pv known dv pv known dv pv known dv pv
Visita v5
Grafos 23
Algoritmo de Dijkstravoid Dijkstra( Vertex s){
Vertex v, w;
s.dist = 0;for( ; ; ){
v = vertice_a_menor_distancia;if( 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 24
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| = Θ(|V|2) e o resultado é satisfatório pois corre em tempo linear no número de arestas
• se o grafo fôr esparso |E| = Θ(|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, podese 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
O(|E| log |V|) actualização dos pesos com operação decreaseKey na filaO(|V| log |V|) percorrer os vértices com operação deleteMin para cada
Tempo de execução total: O(|E| log |V|)
Grafos 25
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 26
Exemplo: custos negativos1 2
3 4 5
6 7
2
5
24
2
6
101
8
2
41
0
1
2
1 2
3 4 5
6 7
2
5
24
2
6
101
8
2
41
0
1
2
1 2
3 4 5
6 7
2
5
24
2
6
101
8
2
41
3
9 5
3
0
0
2
1 2
3 4 5
6 7
2
5
24
2
6
101
8
2
41
2
8 4
2
Achar os caminhosde menor custo acomeçar em 1.
Dijkstra vértice 2 nãoaltera nada …
seria necessário rever 4e propagar as alterações;piora o tempo …
pretendido:
Grafos 27
Algoritmo com custo negativo• 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
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 vif v.dist + c(v,w) < w.dist )
{ w.dist = v.dist + c(v,w);w.path = v;
if(w not in q) )q.enqueue(w);
}}
}
• ciclo de custo negativo ⇒ algoritmo não termina
• teste de terminação: algum vértice sai da fila mais do que |V|+1 vezes
Grafos 28
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 29
Grafos NóActividade
Qual a duração total mínima do projecto?
Quais as actividades que podem ser atrasadas e por quanto tempo (sem aumentar a duração do projecto)?
A(3)
D(2)
E(1)
C(3)
B(2)
F(3)
G(2)
K(4)
H(1)início fim
Nó: actividade e tempo associadoArco: precedência
Grafos 30
Reformulação em Grafo NóEvento
nó = evento
arco = actividade
• evento: fim de actividade
• reformulação introduznós e arcos extra para garantir precedências
6
5
4
7’
8’
9
10’1 6’
3
2
10
7
8
A/3
B/2
C/3
E/1
D/20
0
0
0
0
0
F/3
G/2
0
00
H/1
Nó: evento completar actividadeArco: actividade
K/4
Grafos 31
Menor Tempo de Conclusão
• menor tempo de conclusão ⇔ caminho mais comprido do evento inicial ao nó• 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) )(v, w) ∈ E
6
5
4
7’
8’
9
10’1 6’
3
2
10
7
8
A/3
B/2
C/3
E/1
D/20
0
0
0
0
0
F/3
G/2
0
00
H/1
MTC : usar ordem topológica
0
3
2 3 7
6
5
6
5
9
7
9 10
K/4
3
Grafos 32
Ú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(n) = MTC(n)UTC(v) = min( UTC(w) c(v w) )
(v, w) ∈ E
UTC : usar ordem topológica inversa
6
5
4
7’
8’
9
10’1 6’
3
2
10
7
8
A/3
B/2
C/3
E/1
D/20
0
0
0
0
0
F/3
G/2
0
00
H/10
3
2 3 7
6
5
6
5
9
7
9 10
K/4
3
0
3
4
6
6
5
6
7
9
9
9
9 104
valores calculados em tempo linear mantendo listas de adjacentes e de precedentes dos nós
Grafos 33
Folgas nas actividades
• folga da actividadefolga(v,w) = UTC(w)MTC(v)c(v,w)
6
5
4
7’
8’
9
10’1 6’
3
2
10
7
8
A/3/0
B/2/2
C/3/0
E/1/2
D/2/1
F/3/0
G/2/2
H/1/00
3
2 3 7
6
5
6
5
9
7
9 10
K/4/2
3
0
3
4
6
6
5
6
7
9
9
9
9 104
Caminho crítico: só actividades de folga nula (há pelo menos 1)
Grafos 34
Problemas de fluxo numa rede
Modelar fluxos conservativos entre dois pontos através de canais com capacidade limitada
1 Fluxo num arco não pode ultrapassar a capacidade
2 Soma das entradas num nó igual à soma das saídas
Exemplos• abastecimento de líquido
ponto a ponto• tráfego entre dois pontos
s: fonte; t: poço
distribuição de fluxo pelos arcos arbitrária, desde que respeite as setas
a b
dc
s
t
3 2
1
3 4 2
2 3
a b
dc
s
t
3 2
0
2 1 2
2 3
Grafos 35
Fluxo máximo: 1ª abordagem❏ algoritmo simples de aproximações sucessivas baseado em
• G ➤ grafo base de capacidades• Gf ➤ grafo auxiliar de fluxos
inicialmente fluxos iguais a 0 no fim, fluxo máximo
• Gr ➤ grafo residual (auxiliar) capacidade disponível em cada arco (= capacidade fluxo) capacidade disponível = 0 — eliminar arco saturado
❏ método de calcular o fluxo máximo entre s e t• em cada iteração, seleccionase um caminho em Gr entre s e t (de acréscimo) —
algoritmo não determinístico• valor mínimo nos arcos desse caminho = quantidade a aumentar a cada um dos
arcos respectivos em Gf• recalcular Gr• termina quando não houver caminho de s para t
Grafos 36
Exemplo: estado inicial
a b
dc
s
t
3 2
1
3 4 2
2 3
a b
dc
s
t
0 0
0
0 0 0
0 0
a b
dc
s
t
3 2
1
3 4 2
2 3
G Gf Gr
Grafos 37
Exemplo: 1ª iteração
a b
dc
s
t
3 2
1
3 4 2
2 3
a b
dc
s
t
0 2
0
0 0 2
0 2
a b
dc
s
t
3
1
3 4
2 1
G Gf Gr
Grafos 38
Exemplo: 2ª iteração
a b
dc
s
t
3 2
1
3 4 2
2 3
a b
dc
s
t
2 2
0
2 0 2
2 2
a b
dc
s
t
1
1
1 4
1
G Gf Gr
Grafos 39
Exemplo: 3ª iteração
a b
dc
s
t
3 2
1
3 4 2
2 3
a b
dc
s
t
3 2
0
2 1 2
2 3
a b
dc
s
t
1
1 3
G Gf Gr
Grafos 40
Algoritmo não garante fluxo óptimo❏ critério ganancioso de selecção do caminho: escolher o que dê maior fluxo
caminho s, a, d, t (3 unidades de fluxo) ➤ algoritmo termina sem obter o máximo
exemplo de algoritmo ganancioso que falha
a b
dc
s
t
3 2
1
3 4 2
2 3
a b
dc
s
t
3 0
0
0 3 0
0 3
a b
dc
s
t
2
1
3 1 2
2
Grafos 41
Algoritmo determinísticopermitir que o algoritmo mude de ideias
• para cada arco (v,w) com fluxo f(v,w) no grafo de fluxos acrescentase um arco (w,v) no grafo residual com capacidade f(v,w)
corresponde a deixar devolver fluxo para trás (nunca fica globalmente negativo, contra o arco)
podem existir arcos em sentidos opostos; podem existir ciclos• se as capacidades forem números racionais, o algoritmo termina com máximo• se as capacidades forem inteiros e o fluxo máximo f
bastam f estádios (fluxo aumenta pelo menos 1 por estádio) tempo de execução ( caminho mais curto não pesado ) é O(f. |E| ) ➤ mau
• evitar o problema escolher caminho que dá maior aumento de fluxo semelhante ao problema do caminho pesado mais curto (pequena alteração a Dijkstra) fluxo máximo em O(|E| log capMax) (capMax = capacidade máxima de um arco) cada cálculo de um aumento em O(|E| log |V|) (Dijkstra) global: O(|E|^2 log |V| log capMax)
Grafos 42
Solução óptima 1ª iteração
a b
dc
s
t
3 2
1
3 4 2
2 3
a b
dc
s
t
3 0
0
0 3 0
0 3
a b
dc
s
t
3 2
1
3 1 2
2 3
G Gf Gr
3
3 unidades de fluxo no caminho sadt
Grafos 43
Solução óptima 2ª iteração
a b
dc
s
t
3 2
1
3 4 2
2 3
a b
dc
s
t
3 2
0
2 1 2
2 3
a b
dc
s
t
3 2
1
3 3 2
2 3
G Gf Gr
1
2
2 unidades de fluxo no caminho s,b,d,a,c, t
Grafos 44
Caso difícil
s
a b
t
1
1 000 000
1 000 000
1 000 000
1 000 000
s
a b
t
1
1
1
s
a b
t
1
999 999
999 999
1 000 000
1 000 0001
1
s
a b
t
0
1
1
s
a b
t
1
999 999
999 999
999 999
999 9991
1
se se escolher passar sempre por a e por b…
1
11
1… temos 2 000 000 de iterações, em vez de 2!
Grafos 45
Árvores de expansão mínimas
Árvore que liga todos os vértices do grafo usando arestas com um custo total mínimo
• caso do grafo não dirigido
• grafo tem que ser conexo
• árvore ⇒ acíclico
• número de arestas = |V| 1
❏ exemplo de aplicação: cablamento de uma casa
vértices são as tomadas
arestas são os comprimentos dos troços
Grafos 46
Algoritmo de Prim❏ expandir a árvore por adição sucessiva de arestas e respectivos vértices
• critério de selecção: escolher a aresta (u,v) de menor custo tal que u já pertence à árvore e v não (ganancioso)
• início: um vértice qualquer
❏ idêntico ao algoritmo de Dijkstra para o caminho mais curto
• informação para cada vértice
dist(v) é o custo mínimo das arestas que ligam a um vértice já na árvore
path(v) é o último vértice a alterar dist(v)
known(v) indica se o vértice jé foi processado (isto é, se já pertence à árvore)
• diferença na regra de actualização: após a selecção do vértice v, para cada w não processado, adjacente a v, dist(w) = min{ dist(w), cost(w,v) }
• tempo de execução
O( |V|2 ) sem fila de prioridade
O( |E| log |V| ) com fila de prioridade
Grafos 47
Evolução do algoritmo de Prim
1 2
3 4 5
6 7
7
5
34
2
6
101
8
2
41
1 1
4
1 2
4
12
1 2
3 42
12
1 2
3 4
7
2
12
4
1 2
3 4
6 7
2
12
41
1 2
3 4 5
6 7
2
6
12
41
❶ ❷ ❸ ❹
❺ ❻ ❼
v known dist path1 1 0 02 1 2 13 1 2 44 1 1 15 1 6 76 1 1 77 1 4 4
últimatabela
Grafos 48
Algoritmo de Kruskal❏ analisar as arestas por ordem crescente de peso e aceitar as que não provocarem
ciclos (ganancioso)
❏ método
• manter uma floresta, inicialmente com um vértice em cada árvore (há |V|)
• adicionar uma aresta é fundir duas árvores
• quando o algoritmo termina há só uma árvore (de expansão mínima)
❏ aceitação de arestas — algoritmo de Busca/União em conjuntos
• representados como árvores
• se dois vértices pertencem à mesma árvore/conjunto, mais uma aresta entre eles provoca um ciclo (2 Buscas)
• se são de conjuntos disjuntos, aceitar a aresta é aplicarlhes uma União
❏ selecção de arestas: ordenar por peso ou, melhor, construir fila de prioridade em tempo linear e usar Apaga_Min
• tempo no pior caso O( |E| log |E| ), dominado pelas operações na fila
Grafos 49
Pseudocódigo (Kruskal)void kruskal(){
DisjSet s;PriorityQueue h;Vertex u, v;SetType uset, vset;Edge e,int edgesAccepted = 0;
h = readGraphIntoHeapArray();h.buildHeap();s = new DisjSet(NUM_VERTICES);
while(edgesAccepted < NUM_VERTICES 1 ){
e = h.deleteMin(); // e = (u,v)uset = s.find(u);vset = s.find(v);if (uset != vset) {
edgesAccepted++;S.union(uset, vset);
}}}
Grafos 50
Evolução do algoritmo de Kruskal
❶
❷ ❸
1 2
3 4 5
6 7
7
5
34
2
6
101
8
2
41
1 2
3 4 5
6 7
1 2
3 4 5
6 7
11 2
3 4 5
6 7
1
1
Grafos 51
Evolução do algoritmo de Kruskal
❹
❺ ❻
❼
1 2
3 4 5
6 7
7
5
34
2
6
101
8
2
41
1 2
3 4 5
6 7
2
1
2
1
1 2
3 4 5
6 7
2
1
2
41
1 2
3 4 5
6 7
1
2
1
1 2
3 4 5
6 7
2
6
1
2
41
Grafos 52
Pesquisa em profundidadevoid dfs( Vertex v ) //Depthfirst search
{
v.visited = true;
for each w adjacent to v
if( ! w.visited )
dfs( w );
}
Esquema básico da pesquisa em profundidade
❏ generalização da travessia em préordem
• começando num vértice v, processase v e depois atravessase recursivamente todos os vértices adjacentes a v
• executada numa árvore — visita sistemática de todos os vértices, tempo O(|E|)• executada num grafo arbitrário
— evitar os ciclos ➤ marcar os nós visitados para impedir a repetição
— grafo não dirigido/não conexo ou dirigido/não fortemente conexo: ficando vértices por visitar ➤ percorrer lista de nós até ao seguinte não marcado
Grafos 53
1 Grafos não dirigidos
A
B
C
D E
A
B
C
D E
❏ um grafo não dirigido é conexo ⇔ uma pesquisa em profundidade a começar emqualquer nó visita todos os nós
❏ começase por marcar A; 1º adjacente: B; recorre… ao processar (v,w), se w não estiver marcado acrescentase a aresta na árvore se já estiverem ambos marcados, acrescentase uma aresta de retorno (a ponteado)
que não pertence à árvore (todas as arestas do grafo estão na árvore total)❏ árvore simula a pesquisa; numeração em préordem pelas arestas da árvore dá a ordem de
marcação dos vértices
grafo árvore deexpansão emprofundidade
Grafos 54
2 Biconectividade
Grafo conexo não dirigido é biconexo se
não existe nenhum vértice cuja remoção torne o resto do grafo desconexo
❏ Aplicação rede com tolerância a falhas
❏ Pontos de articulação vértices que tornam o grafo desconexo (críticos)
❏ Algoritmo de detecção de pontos de articulação em tempo linear
• início num vértice qualquer
• pesquisa em profundidade, numerando os vértices ao visitálos — Num(v), em préordem
• para cada vértice na árvore de expansão calcular Low(v), o menor número de vértice que se atinge com zero ou mais arestas na árvore e possivelmente uma aresta de retorno (computável com travessia em pósordem)
Grafos 55
Pontos de articulação
❏ Cálculo de Low(v) primeiro para os filhos e depois para o pai
• arestas (v,w) são da árvore se Num(v) < Num(w); de retorno no caso inverso
• basta percorrer a lista de adjacências; O( |E| + |V| )
❏ Vértice v é ponto de articulação se tiver um filho w tal que Low(w) ≥ Num(v)
❏ A raiz é ponto de articulação sse tiver mais que um filho na árvore
❏ Low(v) é mínimo de• Num(v)• o menor Num(w) de todas as arestas (v,w) de retorno• o menor Low(w) de todos as arestas (v,w) da árvore
Grafos 56
Detecção de pontos de articulação
Pontos de articulação: C e D
AB
C D F
A,1/1
B,2/1
C,3/1
D,4/1 G,7/7
grafo árvores deexpansão emprofundidade
EG
E,5/4F,6/4
A,5/1
B,6/1
C,1/1
D,2/1 G,7/7
E,3/2F,4/2
v, Num(v)/Low(v)
Grafos 57
Três passagens?
• Num(v) — preordem
• Low(v) — posordem
• pontos de articulação — posordem combinados
// Atribui numero e calcula pai
// Contador global e inicializado a 1
void assignNum( Vertex v){
v.num = counter++;v.visited = true;for each w adjacent to v
if( !w.visited ){
w.parent = v;assignNum(w);
}}
// Atribui Low
// Testa Pontos de Articulação
void assignLow( Vertex v){
v.low = v.num; //regra 1for each w adjacent to v
if(w.num > v.num) //ramo árvore{
assignLow(w);if( w.low >= v.num )
System.out.println(v, “ Ponto de articulação”);
v.low = min(v.low, w.low); //regra 3}elseif ( v.parent != w ) //retorno
v.low = min(v.low, w.num); //regra 2}
Grafos 58
Uma só pesquisa em profundidade
Combina o préprocessamento e o pósprocessamento numa única passagem
// Procura Pontos de Articulação// Contador global e inicializado a 1 void findArt( Vertex v){
v.visited = true;v.low = v.num = counter++; //regra 1for each w adjacent to v
if( !w.visited ) //ramo árvore{
w.parent = v;findArt(w);if(w.low >= v.num )
System.out.println(v, “ Ponto de articulação”);
v.low = min(v.low, w.low); //regra 3}elseif ( v.parent != w ) //retorno
v.low = min(v.low, w.num); //regra 2}
Grafos 59
3 Circuitos de EulerPuzzle: desenhar as figuras abaixo sem levantar o lápis e sem repetir arestas; de
preferência, terminando no mesmo vértice em que iniciar.
Reformulação do problema em Teoria de Grafos: pôr um vértice em cada intersecção
Caminho de Euler: caminho que visita cada aresta exactamente uma vez
problema resolvido por Euler em 1736 e que marca o início da Teoria dos Grafos
Grafos 60
Solução❏ condição necessária
• circuito de Euler: número de arestas convergentes em cada vértice é par o ciclo entra tantas vezes em vértices quantas sai
• caminho de Euler: idem, excepto possivelmente em dois vértices o primeiro e o último; no caso de haver mais vértices com número
ímpar de arestas é impossível❏ condição suficiente
• se se verificarem as condições acima, então existe circuito (caminho) de Euler
❏ método: pesquisa em profundidade O(|E| + |V| )• principal problema: fazer um curtocircuito e deixar arestas de fora• correcção
procurar o primeiro vértice no caminho obtido que possua uma aresta não percorrida
lançar uma subpesquisa em profundidade inserir o resultado no caminho principal (usar lista ligada)
❏ Ciclo Hamiltoniano: ciclo simples que visita todos os vértices? (vêse depois)
Grafos 61
Exemplo de um circuito1
12
7
4 5
1198
2 3
10
6Grafo: existe caminho de Euler
1
12
7
4 5
1198
2 3
10
6Depois de fazer caminho5, 4, 10, 5
Grafos 62
Exemplo de um circuito1
12
7
4 5
1198
2 3
10
6Depois de fazer caminho5, 4, 1,3,7,4,11,10,7,9,3,4,10, 5
1
12
7
4 5
1198
2 3
10
6Depois de fazer caminho5, 4, 1, 3, 2, 8, 9, 6, 3, 7, 4, 11, 10, 7, 9, 3, 4, 10, 5
Grafos 63
4 Grafos dirigidos
❏ (também) atravessáveis em tempo linear por pesquisa em profundidade (serve para detectar se grafo é acíclico)
❏ problema: se não for fortemente conexo, pesquisa em profundidade pode não visitar todos os nós ⇒ recomeçar a pesquisa num nó não visitado (nova raiz…)
A B
D C
E
F
G
H
J I
Grafos 64
Árvore de expansão
❏ pesquisa em profundidade induz uma árvore/floresta de expansão
❏ para além das arestas genuínas da árvore, há arestas para nós já marcados
arestas de retorno para um antepassado — (A,B), (I,H)
arestas de avanço para um descendente — (C,D), (C,E)
arestas cruzadas para um nó não relacionado — (F,C), (G,F)
• alguns algoritmos necessitam de distinguir estas categorias de arestas
A
B
C F
D
E
H
J
I
G
Grafos 65
Componentes fortemente conexos❏ Método:
• pesquisa em profundidade no grafo G determina floresta de expansão, numerando vértices em pósordem
• inverter todas as arestas de G — Gr
• segunda pesquisa em profundidade, em Gr, começando sempre pelo vértice de numeração mais alta ainda não visitado
❏ cada árvore obtida é um componente fortemente conexo, i.e., a partir de um qualquer dos nós pode chegarse a todos os outros
❏ Prova• mesmo componente ⇒ mesma árvore de expansão
se dois vértices v e w estão no mesmo componente, há caminhos de v para w e de w para v em G e em Gr; se v e w não pertencerem à mesma árvore de expansão, também não estão no mesmo componente
• mesma árvore de expansão ⇒ mesmo componentei.e., há caminhos de v para w e de w para v ou, equivalentemente, se x for a raiz de uma árvore de expansão em profundidade, há caminhos de x para v e de v para x, de x para w e de w para x e portanto entre v e w
como v é descendente de x na árvore de Gr, há um caminho de x para v em Gr, logo de v para x em G; como x é a raiz tem o maior número de pósordem na primeira pesquisa; portanto, na primeira pesquisa, todo o processamento de v se completou antes de o trabalho em x ter terminado; como há um caminho de v para x, seguese que v tem que ser um descendente de x na árvore de expansão — caso contrário v terminaria depois de x; isto implica um caminho de x para v em G.
Grafos 66
Componentes fortemente conexos
A,3 B,6
D,2 C,4
E,1
F,5
G,10
H,9
J,8 I,7
Gr: obtido de G por inversão de todas as arestasNumeração: da travessia de G em pósordem
Grafos 67
Componentes fortemente conexos
A
B
C
F
D EH
J
I
G
Travessia em pósordem de GrComponentes fortemente conexos: {G}, {H, I, J}, {B, A, C, F}, {D}, {E}