Análise e Síntese de Algoritmos
Algoritmos em Grafos
CLR, Cap. 22
Resumo
• Algoritmos elementares em grafos
– Representação de grafos
– Procura em Largura Primeiro
• Breadth-First Search (BFS)
– Propriedades da BFS
– Procura em Profundidade Primeiro
• Depth-First Search (DFS)
– Propriedades da DFS
– Ordenação Topológica
– Componentes Fortemente Ligados
• Strongly Connected Components (SCCs)
– Exemplos
2003/2004
Análise e Síntese de Algoritmos
2
Grafos — Definição e Representação
• Grafo definido por um conjunto V de vértices e um
conjunto E de arcos, G = (V, E)
– Arcos representam ligações entre pares de vértices
• EVV
– Grafo esparso: |E| << |V  V|
– Representação dos arcos
• Matriz de adjacências: arcos representados por matriz
– Para grafos densos
• Listas de adjacências: arcos representados por listas
– Para grafos esparsos
• Grafos podem ser dirigidos ou não dirigidos
– Existência (ou não) da noção de direcção nos arcos
2003/2004
Análise e Síntese de Algoritmos
3
Grafos — Definição e Representação
• Listas vs. Matriz de adjacências
Não Dirigido:
1
3
2
4
1
2
3
4
2
1
2
1
4
3
2
4
-
1
2
3
4
2
3
2
4
-
-
1
2
3
4
1
0
1
0
1
2
1
0
1
1
3
0
1
0
0
4
1
1
0
0
1
2
3
4
1
0
0
0
0
2
1
0
0
1
3
0
1
0
0
4
1
0
0
0
Dirigido:
1
3
2
4
2003/2004
Análise e Síntese de Algoritmos
4
Grafos — Definição e Representação
• Listas de adjacências:
– Grafos não dirigidos
• Tamanho das listas é 2 E
– Grafos dirigidos
• Tamanho das listas éE
 Tamanho total das listas de adjacências é O(V+E)
• Grafos pesados:
– Função de pesos: w: E  R
• Permite associar peso com cada arco
2003/2004
Análise e Síntese de Algoritmos
5
Procura em Largura Primeiro (BFS)
• Dados G = (V, E) e vértice fonte s, BFS explora
sistematicamente vértices de G para descobrir todos
os vértices atingíveis a partir de s
– Cálculo da distância: menor número de arcos de s para
cada vértice atingível
– Identificação de árvore BF: caminho mais curto de s para
cada vértice atingível v
• Fronteira entre nós descobertos e não descobertos é
expandida uniformemente
– Nós à distância k descobertos antes de qualquer nó à
distância k+1
2003/2004
Análise e Síntese de Algoritmos
6
Procura em Largura Primeiro (BFS)
• Implementação:
– color[v]: cor do vértice v, branco, cinzento e preto
– p[v]: predecessor de v na árvore BF
– d[v]: tempo de descoberta de v
• Outras definições:
– d(s,v): menor distância de s a v
• menor número de arcos em qualquer caminho de s para v
2003/2004
Análise e Síntese de Algoritmos
7
Procura em Largura Primeiro (BFS)
• Algoritmo:
function BFS(G,s)
for each vertex u  in V[G] - { s }
inicializações
color[u] = white; d[u] = ; p[u] = NIL
color[s] = gray; d[s] = 0; p[s] = NIL
Q={s}
while Q  
u = Head[Q]
ciclo
for each v  Adj[u]
principal
if color[v] = white
color[v] = gray; d[v] = d[u] + 1; p[v] = u
Enqueue (Q, v)
Dequeue (Q)
color[u] = black
2003/2004
Análise e Síntese de Algoritmos
8
Procura em Largura Primeiro (BFS)
• Tempo de execução: O(V + E)
– Inicialização: O(V)
– Para cada vértice
• Colocado na fila apenas 1 vez:
• Lista de adjacências visitada 1 vez:
O(V)
O(E)
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
9
Procura em Largura Primeiro (BFS)
• Resultado:
– Para qualquer arco (u,v): ds, v   ds,u  1
• Se u atingível, então v atingível
– caminho mais curto para v não pode ser superior a
caminho mais curto para u mais arco (u,v)
• Se u não atingível, então resultado é válido
(independentemente de v ser atingível)
• …
• No final da BFS:
– d[u] = d(s,u), para todo o vértice u de V
2003/2004
Análise e Síntese de Algoritmos
10
Procura em Largura Primeiro (BFS)
• Árvores BF: (sub-grafo de G)
– Vértices atingíveis a partir de s
– Arcos que definem a relação predecessor da BFS
Gp  Vp ,E p 
Vp  v  V : pV   NIL  s
2003/2004
E p  pv , v   E : v  Vp  s
Análise e Síntese de Algoritmos
11
Procura Profundidade Primeiro (DFS)
• Grafo pesquisado dando prioridade aos arcos dos
vértices mais recentemente visitados
• Resultado da procura:
– Floresta DF:
Gp  V,Ep 
E p  pv , v  : v  V  pv   NIL
– Floresta DF composta por várias árvores DF
• Implementação:
– color[u]: cor do vértice (branco, cinzento, preto)
– d[u]: tempo de início (de visita do vértice)
– f[u]: tempo de fim (de visita do vértice)
2003/2004
Análise e Síntese de Algoritmos
12
Procura Profundidade Primeiro (DFS)
• Algoritmo:
function DFS(G)
for each vertex u  V[G]
color[u] = white; p[u] = NIL
time = 1
for each vertex u  V[G]
if color[u] = white
DFS-Visit(u)
function DFS-Visit(u)
color[u] = gray; d[u] = time; time = time + 1
for each v  Adj[u]
if color[v] = white
p[v] = u; DFS-Visit(v)
color[u] = black; f[u] = time; time = time + 1
2003/2004
Análise e Síntese de Algoritmos
13
Procura Profundidade Primeiro (DFS)
• Tempo de execução: O(V+E)
– Inicialização: O(V)
– Chamadas a DFS-Visit dentro de DFS: O(V)
– Arcos analisados em DFS-Visit: (E)
• Chamadas a DFS-Visit dentro de DFS-Visit: O(V)
• Exemplo:
2003/2004
Análise e Síntese de Algoritmos
14
Procura Profundidade Primeiro (DFS)
• Resultado:
– Numa DFS de G = (V, E), para cada par de vértices u e v
apenas um dos 3 casos seguintes é verdade:
• Os intervalos [d[u], f[u]] e [d[v], f[v]] são disjuntos
• [d[u], f[u]] está contido em [d[v], f[v]] e u é descendente de
v na árvore DF
• [d[v], f[v]] está contido em [d[u], f[u]] e v é descendente de
u na árvore DF
1
d[v]
d[u]
v é descendente de u
( f[v] < f[u] )
f[u]
f[v]
d[v]
intervalos são disjuntos
f[u]
2003/2004
d[v]
Análise e Síntese de Algoritmos
15
Procura Profundidade Primeiro (DFS)
• Classificação de arcos (u,v):
– Arcos de árvore: (tree edges)
• arcos na floresta DF, Gp
– (u,v) é arco de árvore se v foi visitado devido ao arco (u,v) ser
visitado
– Arcos para trás: (back edges)
• ligam vértice u a vértice v antecessor na mesma árvore DF
– Arcos para a frente: (forward edges)
• ligam vértice v a vértice descendente na mesma árvore DF
– Arcos de cruzamento: (cross edges)
• Na mesma árvode DF, se u (ou v) não antecessor de v (ou u)
• Entre árvores DF diferentes
2003/2004
Análise e Síntese de Algoritmos
16
Procura Profundidade Primeiro (DFS)
• Classificação de cada arco (u,v):
– Arco de árvore:
• d[u]  d[v]  f[v]  f[u] ; color[v] = white; visita v a partir de u
– Arco para trás:
• d[v]  d[u]  f[u]  f[v] ; color[v] = gray
– Arco para a frente:
• d[u]  d[v]  f[v]  f[u] ; color[v] = black
– Arco de cruzamento:
• d[v]  f[v]  d[u]  f[u] ; color[v] = black
2003/2004
Análise e Síntese de Algoritmos
17
Procura Profundidade Primeiro (DFS)
• Dado G = (V, E), não dirigido, cada arco é arco de
árvore ou arco para trás
– i.e., não existem arcos para a frente e de cruzamento
• Numa floresta DFS, v é descendente de u se e só se
quando u é descoberto existe um caminho de
vértices brancos de u para v
– v descendente de u  existe caminho de vértices brancos
de u para v
• Qualquer vértice w descendente de u verifica [d[w], f[w]]
 [d[u], f[u]], pelo que w é branco quando u é descoberto
– …
2003/2004
Análise e Síntese de Algoritmos
18
Recapitular
• Representação de grafos
– Listas de adjacências
– Matrizes de adjacências
• Procuras em grafos
– BFS
• Tempos de descoberta (d[])
– DFS
• Tempos de início (d[]) e de fim (f[])
2003/2004
Análise e Síntese de Algoritmos
19
Definições
• Dado grafo G = (V, E), um caminho p é uma
sequência <v0,v1,…,vk> tal que para todo o i, 0ik-1,
(vi,vi+1)E
• Se existe um caminho p de u para v,então v diz-se
atingível a partir de u via p
• Um ciclo num grafo G = (V,E) é um caminho
<v0,v1,…,vk>, tal que v0 = vk
• Um grafo dirigido G = (V,E) diz-se acíclico se não
tem ciclos
– Directed acyclic graph (DAG)
2003/2004
Análise e Síntese de Algoritmos
20
Ordenação Topológica
• Uma ordenação topológica de um DAG G=(V,E) é
uma ordenação de todos os vértices tal que se
(u,v)E então u aparece antes de v na ordenação
• Algoritmos:
– Eliminação de vértices
– Utilizando informação de DFS
2003/2004
Análise e Síntese de Algoritmos
21
Ordenação Topológica (Cont.)
• Algoritmo:
function Topological-Sort-1(G)
L=
// Lista de vértices
Q=
// Fila de vértices
for each v  G
if v sem arcos de entrada (w,v)
Enqueue(Q,v)
while Q  
u = Head(Q)
Eliminar todos os arcos (u,v)
if v sem arcos de entrada (w,v)
Colocar
Enqueue(Q,v)
vértices em L
Dequeue(Q)
Colocar u no fim da lista L
O(V+E)
2003/2004
Análise e Síntese de Algoritmos
Inicialização
O(V)
22
Ordenação Topológica (Cont.)
• Algoritmo:
function Topological-Sort-2(G)
Executar DFS(G) para cálculo do tempo de fim f[v] para cada v
Para cada vértice terminado, inserir no princípio de lista ligada
return lista ligada de vértices
• Tempo de execução
– DFS: O(V+E)
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
23
Ordenação Topológica (Cont.)
• Intuição:
1
3
2
4
Na DFS:
Tempo de fim de 3 é sempre  Tempo de fim de 4
Tempo de fim de 2 é sempre  Tempo de fim de 4
Tempo de fim de 1 é sempre  Tempo de fim de 2,4
Sem ciclos, se existe caminho de u para v, verifica-se
sempre f[u]  f[v] !
2003/2004
Análise e Síntese de Algoritmos
24
Componentes Fortemente Ligados
• Definição:
– Dado grafo dirigido G = (V,E) um componente fortemente ligado
(SCC) é um conjunto máximo de vértices U  V, tal que para
u,vU, u é atingível a partir de v, e v é atingível a partir de u
• Obs: vértice simples é SCC
• Outras definições:
– Grafo transposto de G = (V,E)
• GT = (V, ET) tal que: E T  u, v  : v,u  E
– OBS: G e GT têm os mesmos SCCs
2003/2004
Análise e Síntese de Algoritmos
25
Componentes Fortemente Ligados
• Algoritmo:
function SCCs(G)
Executar DFS(G) para cálculo do tempo de fim f[v] para cada v
Representar GT
Executar DFS(GT)
(no ciclo principal de DFS considerar os vértices por
ordem decrescente de tempo de fim de DFS(G))
Cada árvore de DFS encontrada corresponde a novo
SCC
• Tempo de execução: O(V+E)
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
26
Componentes Fortemente Ligados
• Intuição:
Em G:
SCC 1
maior f
Em GT:
2003/2004
SCC 2

maior f
SCC 3

maior f
SCC 1
SCC 2
SCC 3
árvore DFS
árvore DFS
árvore DFS
Análise e Síntese de Algoritmos
27
Componentes Fortemente Ligados
1
G:
2
5
3
6
9
7
10
11
f[] = 24
4
GT:
4
max f > max f
8
1
2
2003/2004
max f > max f
12
5
3
6
9
7
8
Análise e Síntese de Algoritmos
10
11
12
28
Problemas
• Algoritmo eficiente para determinar se grafo G = (V, E)
é bipartido ?
– Grafo G é bipartido se V pode ser dividido em L e R, tal que
todos os arcos de G incidentes em 1 vértice de L e 1 vértice
de R
• Algoritmo eficiente para calcular o diâmetro de uma
árvore T = (V, E) ?
– Diâmetro: max du, v 
u,vV
– Sol. 1: Duas BFSs
– Sol. 2: Vértice adicional e 1 BFS
2003/2004
Análise e Síntese de Algoritmos
29
Outro Problema
• Algoritmo eficiente para determinar se um grafo
G=(V, E) é semi-ligado
– Um grafo dirigido G = (V,E) diz-se semi-ligado se para
qualquer par de vértices (u,v), u atingível a partir de v ou v
atingível a partir de u
2003/2004
Análise e Síntese de Algoritmos
30
Revisão
• Algoritmos elementares em grafos
– Representação de grafos
– BFS; DFS
• Algoritmos
• Propriedades
– Aplicações:
• Ordenação topológica
• Componentes fortemente ligados
• A seguir:
– Estruturas de dados para conjuntos disjuntos (CLRS, Cap. 21)
– Árvores abrangentes de menor custo (CLRS, Cap. 23)
2003/2004
Análise e Síntese de Algoritmos
31