Análise e Síntese de Algoritmos Algoritmos em GrafosCLR, Cap. 22

Análise e Síntese de Algoritmos

Algoritmos em Grafos CLR, Cap. 22

2003/2004 Análise e Síntese de Algoritmos 2

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


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



• Listas vs. Matriz de adjacências

1 2 4 -2 1 3 43 2 - -4 1 2 -

1

2 4

3

1

2 4

3 1 2 4 -2 3 - -3 - - -4 2 - -

1 2 3 41 0 1 0 12 1 0 1 13 0 1 0 04 1 1 0 0

1 2 3 41 0 1 0 12 0 0 1 03 0 0 0 04 0 1 0 0

Não Dirigido:

Dirigido:



• 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


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



• Implementação:– color[v]: cor do vértice v, branco, cinzento e preto– [v]: predecessor de v na árvore BF– d[v]: tempo de descoberta de v

• Outras definições:– (s,v): menor distância de s a v

• menor número de arcos em qualquer caminho de s para v



• Algoritmo:

function BFS(G,s)for each vertex u in V[G] - { s }

color[u] = white; d[u] = ; [u] = NILcolor[s] = gray; d[s] = 0; [s] = NILQ = { s }while Q

u = Head[Q]for each v Adj[u]

if color[v] = whitecolor[v] = gray; d[v] = d[u] + 1; [v] = uEnqueue (Q, v)

Dequeue (Q)color[u] = black

inicializações

cicloprincipal



• Tempo de execução: O(V + E)– Inicialização: O(V)– Para cada vértice

• Colocado na fila apenas 1 vez: O(V)• Lista de adjacências visitada 1 vez: O(E)

• Exemplo



• Resultado:– Para qualquer arco (u,v):

• 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] = (s,u), para todo o vértice u de V

1u,sv,s



• Árvores BF: (sub-grafo de G)– Vértices atingíveis a partir de s– Arcos que definem a relação predecessor da BFS

sNILV:VvV sVv:Ev,vE

E,VG


Procura Profundidade Primeiro (DFS)

• Grafo pesquisado dando prioridade aos arcos dos vértices mais recentemente visitados

• Resultado da procura:– Floresta DF:

– 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)

E,VG NILvVv:v,vE



• Algoritmo:function DFS(G)

for each vertex u V[G]color[u] = white; [u] = NIL

time = 1for each vertex u V[G]

if color[u] = whiteDFS-Visit(u)

function DFS-Visit(u)color[u] = gray; d[u] = time; time = time + 1for each v Adj[u]

if color[v] = white[v] = u; DFS-Visit(v)

color[u] = black; f[u] = time; time = time + 1



• 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:



• 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

d[u] d[v]

d[v] f[u]v é descendente de u( f[v] < f[u] )

f[u] d[v]intervalos são disjuntos

1

f[v]



• Classificação de arcos (u,v):– Arcos de árvore: (tree edges)

• arcos na floresta DF, G – (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



• 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



• 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 – …


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[])


Definições

• Dado grafo G = (V, E), um caminho p é uma sequência <v0,v1,…,vk> tal que para todo o i, 0ik-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)


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


Ordenação Topológica (Cont.)

• Algoritmo:function Topological-Sort-1(G)

L = // Lista de vérticesQ = // Fila de vérticesfor 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)

Enqueue(Q,v)Dequeue(Q)Colocar u no fim da lista L

InicializaçãoO(V)

Colocarvértices em LO(V+E)



• Algoritmo:

• Tempo de execução– DFS: O(V+E)

• Exemplo

function Topological-Sort-2(G)Executar DFS(G) para cálculo do tempo de fim f[v] para cada vPara cada vértice terminado, inserir no princípio de lista ligadareturn lista ligada de vértices



• Intuição:

1

2 4

3

Na DFS:Tempo de fim de 3 é sempre Tempo de fim de 4Tempo de fim de 2 é sempre Tempo de fim de 4Tempo 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] !


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,vU, 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:

– OBS: G e GT têm os mesmos SCCs

Eu,v:v,uET



• Algoritmo:

• Tempo de execução: O(V+E)• Exemplo

function SCCs(G)Executar DFS(G) para cálculo do tempo de fim f[v] para cada vRepresentar 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



• Intuição:

SCC 1 SCC 2 SCC 3

maior f maior f maior f

Em G:

Em GT: SCC 3SCC 2SCC 1

árvore DFS árvore DFS árvore DFS



G:1

2

4

3

5

6

8

7

9

10

12

11

1

2

4

3

5

6

8

7

9

10

12

11

GT:

f[] = 24max f > max fmax f > max f


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:

– Sol. 1: Duas BFSs– Sol. 2: Vértice adicional e 1 BFS

v,u maxVv,u


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


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)

Documents

Análise e Síntese de Algoritmos Algoritmos em GrafosCLR, Cap. 22