› ~yandre › AEDEP › grafos-grande.pdf · GRAFOS - Plone site2008-09-17 · Prof. Yandre...

Prof. Y

andre M

aldonado-

1

•• GRAFOSGRAFOS•• IntroduIntroduçção;ão;

•• RepresentaRepresentaçção em Memão em Memóória;ria;

•• Algoritmo de Algoritmo de DijkstraDijkstra..

Prof. Yandre Maldonado e Gomes da Costa

UNIVERSIDADE ESTADUAL DE MARINGÁDEPARTAMENTO DE INFORMÁTICA

Prof. Y

andre M

aldonado-

2

GRAFOS

• Definição:– G (V, E), onde:

• V é um conjunto de vértices (ou nodos);– |V| denota o número de elementos de V;

• E é uma coleção de pares de V, chamados de aresta (ou arco);

– |E| denota o número de elementos de E;

– As arestas descrevem relações entre os vértices;

– Exemplo: relações de co-autoria;Goodrich Tamassia

Preparata

Di Battista

Chiang

Prof. Y

andre M

aldonado-

3

GRAFOS

• Terminologia:– Incidência: a aresta (u,v) é dita incidente à u e a v;– Adjacência: dois vértices u e v são adjacentes se

existe aresta (u,v);– Grau do vértice: o grau de um vértice é igual ao

número de arestas que incidem a ele;

• Representação geométrica de grafos:

ab

ed

c

Prof. Y

andre M

aldonado-

4

GRAFOS

• Terminologia (cont.):– Caminho: um caminho do vértice v1 ao vértice

vk é uma seqüência de vértices v1...vk tal que (vj,vj+1) pertence a E, 1<=j<=k-1;

– Comprimento de um caminho: número de arestas percorridas no caminho;

• Neste exemplo d, e, b, a é um caminho de comprimento igual a 3;

ab

ed

c

Prof. Y

andre M

aldonado-

5

GRAFOS

• Terminologia (cont.):– Ciclo: é um caminho v1, v2 ... vk, vk+1, onde

v1 = vk+1 e k>=3;• Neste exemplo b, c, e, b é um caminho;

– Grafo acíclico: grafo sem ciclos;

ab

ed

c

Prof. Y

andre M

aldonado-

6

GRAFOS

• Grafo conexo: grafo que possui caminho entre cada par de vértices de V;

• Grafo desconexo: grafo não conexo;

ab

ed

c ab

e d

c

Conexo Desconexo

Prof. Y

andre M

aldonado-

7

GRAFOS

• Grafo completo: grafo que possui uma aresta entre cada par de seus vértices;

a

b

e d

c

Prof. Y

andre M

aldonado-

8

GRAFOS

• Subgrafo: G2 (V2,E2) é subgrafo de G1(V1,E1) se:– V2 está contido em V1;– E2 está contido em E1;

ab

ed

c

G1

ab

e

c

G2

G2 é subgrafo de G1

Prof. Y

andre M

aldonado-

9

GRAFOS

• Grafo Direcionado (ou Dígrafo)– Grafo em que as arestas são pares

ordenados;– Neste caso (u,v) é diferente de (v,u);– Exemplo:

• V={a, b, c, d, e}• E={(a,b), (a,e), (c,b), (d,e), (e,b), (e,c), (e,d)}

ab

ed

c

Prof. Y

andre M

aldonado-

10

GRAFOS

• Grafo Direcionado– Exemplo de aplicação: representação de

malha aérea (linhas entre aeroportos).

MGF

LDB

POA

CWB

CGH

GOL-378

TAM-828

RSL-126 BRA-453GOL-396

TAM-524

TAM-704

RSL-122

Prof. Y

andre M

aldonado-

11

GRAFOS

• Grafo Direcionado:– Grau de entrada de v: número de arestas

convergentes a v;• O grau de entrada de b é 3;

– Grau de saída de v: número de arestas divergentes de v;

• O grau de saída de a é 2;

ab

ed

c

Prof. Y

andre M

aldonado-

12

GRAFOS

• Grafo ponderado: grafo em que se associa um valor (ou peso) a cada aresta;– O peso de uma aresta e é denotado por w(e)

• w(Maringá, Paranavaí)=70

Maringá

MandaguariParanavaí

Cianorte

70

7570

35

Prof. Y

andre M

aldonado-

13

GRAFOS

• Representação de grafos:– Matriz de adjacências;– Matriz de incidências;– Lista de adjacências;

Prof. Y

andre M

aldonado-

14

GRAFOS

• Matriz de adjacências– Para um grafo G (V,E):

• Cria-se uma matriz M com dimensões |V| x |V|;• Cada linha i e cada coluna j é associada à um vértice

do grafo e:

– M[i,j]=1 se (vi, vj) ∈ E;– M[i,j]=0 se (vi, vj) ∉ E;

– Desvantagem: ocupa |V|2 posições na memória;– Vantagem: acesso rápido à informação sobre

uma aresta;

Prof. Y

andre M

aldonado-

15

GRAFOS

• Exemplo de Matriz de adjacências

• Observe que:– Em grafo não direcionado a matriz é simétrica;– O número de 1’s é igual a 2 |E|;

ab

ed

c

01111e

10000d

10010c

10101b

10010a

edcba

Prof. Y

andre M

aldonado-

16

GRAFOS

• Matriz de adjacências para um dígrafo

• Observe que:– O número de 1’s é igual a |E|;

01110e

10000d

00010c

00000b

10010a

edcba

ab

ed

c

Prof. Y

andre M

aldonado-

17

GRAFOS

• Matriz de adjacências para um grafo ponderado:– Coloca-se em M[i,j] o valor de w(ei,ej);

Maringá

MandaguariParanavaí

Cianorte

70

7570

35

070070PVI

7003575MGA

03500MRI

707500CNE

PVIMGAMRICNE

Prof. Y

andre M

aldonado-

18

GRAFOS

• Matriz de incidências– Para um grafo G (V,E):

• Cria-se uma matriz M com dimensões |V| x |E|;• Associa-se cada linha i e com um vértice e cada

coluna j com uma aresta do grafo e:– M[i,j]=1 se j incide em i;– M[i,j]=0 caso contrário;

– Desvantagem: é preciso conhecer antecipadamente o número de vértices e arestas do grafo;

Prof. Y

andre M

aldonado-

19

GRAFOS

• Exemplo de Matriz de incidências

• Observe que:– Em cada coluna da matriz existem

dois 1’s;– Em cada linha da matriz o número de

1’s é igual ao grau do vértice;

111010e

100000d

010100c

001101b

000011a

654321

ab

ed

c1 3

24 5

6

Neste caso estes números não são pesos, são identificadores das arestas.

Prof. Y

andre M

aldonado-

20

GRAFOS

• Matriz de incidências para dígrafo

-1-11010e

10-1000d

010-100c

000101b

0000-1-1a

654321

Neste caso estes números não são pesos, são identificadores das arestas.

ab

ed

c1

25

3

6

4

Prof. Y

andre M

aldonado-

21

GRAFOS

• Lista de adjacências– Consiste em um vetor com |V| listas encadeadas;– Cada lista corresponde à um vértice, e armazena os

vértices que são adjacentes a ele;– Exemplo:

– Gasto de memória: |V| + 2|E|

ab

ed

c

e

d

c

b

a b e

a c e

b e

e

a b c d

Prof. Y

andre M

aldonado-

22

GRAFOS

• Lista de adjacências para dígrafos– Exemplo:

– Gasto de memória: |V| + |E|

e

d

c

b

a b e

b

e

b c d

ab

ed

c

Prof. Y

andre M

aldonado-

23

• Um problema clássico em grafos:– Menor caminho de origem única:

• Para grafos sem pesos: busca em amplitude (ou em largura);

• Para grafos ponderados e sem pesos negativos: algoritmos de Dijkstra;

GRAFOS

Prof. Y

andre M

aldonado-

24

GRAFOS

• Busca em Amplitude– Encontra o menor caminho a partir de um

vértice inicial para qualquer outro vértice do grafo;

– Algoritmo da busca em amplitude:1. Inicialmente marca-se o vértice de origem como

visitado;2. Coloca-se todos os seus vértices adjacentes ainda

não visitados em uma fila F;3. Retira-se o primeiro vértice da fila, marcando-o

como visitado. Repete-se o processo a partir do passo 2, até que não haja mais vértice ainda não visitado.

Prof. Y

andre M

aldonado-

25

GRAFOS

• Exemplo de busca em amplitude:– Grafo sem pesos;– Utilizaremos um vetor auxiliar P para

identificar os predecessores de cada vértice marcado;

– Os vértices já visitados serão identificados com sombreamento.

ab

fe

cd

g

h

Prof. Y

andre M

aldonado-

26

GRAFOS

• Exemplo de busca em amplitude:– Vértice de origem: a;

ab

fe

cd

g

h

-aa---a#

hgfedcbaP

gfbFila

Prof. Y

andre M

aldonado-

27

GRAFOS

• Exemplo de busca em amplitude:

ab

fe

cd

g

h

-aa--ba#

hgfedcbaP

cgfFila

Prof. Y

andre M

aldonado-

28

GRAFOS

• Exemplo de busca em amplitude:

ab

fe

cd

g

h

-aaf-ba#

hgfedcbaP

ecgFila

Prof. Y

andre M

aldonado-

29

GRAFOS

• Exemplo de busca em amplitude:

ab

fe

cd

g

h

gaaf-ba#

hgfedcbaP

hecFila

Prof. Y

andre M

aldonado-

30

GRAFOS

• Exemplo de busca em amplitude:

ab

fe

cd

g

h

gaaf-ba#

hgfedcbaP

heFila

Prof. Y

andre M

aldonado-

31

GRAFOS

• Exemplo de busca em amplitude:

ab

fe

cd

g

h

gaafeba#

hgfedcbaP

dhFila

Prof. Y

andre M

aldonado-

32

GRAFOS

• Exemplo de busca em amplitude:

ab

fe

cd

g

h

gaafeba#

hgfedcbaP

dFila

Prof. Y

andre M

aldonado-

33

GRAFOS

• Exemplo de busca em amplitude:

ab

fe

cd

g

h

gaafeba#

hgfedcbaP

FilaTérmino: fila vazia e todos os vértices visitados.

Prof. Y

andre M

aldonado-

34

GRAFOS

• Descobre-se o menor caminho a partir de P, da seguinte forma:– Caminho de a até d: seqüência inversa dos

predecessores a partir de d até chegar em a;

gaafeba#

hgfedcbaP

d – e – f – a

a – f – e - d

Prof. Y

andre M

aldonado-

35

GRAFOS

• Algoritmo de Dijkstra– Desenvolvido por Edsger Dijkstra em 1959;– Aplicações:

• Distribuição de pacotes em rede de computadores com a melhor velocidade possível;

• Encontrar o caminho mais curto entre cidades;

Prof. Y

andre M

aldonado-

36

• Algoritmos de Dijkstra:– Para encontrar o menor caminho de origem

única;– Para um grafo:

• Conexo;• Ponderado (com pesos positivos);

– Encontra o caminho entre v e qualquer outro vértice do grafo com a menor soma acumulada de pesos;

GRAFOS

Prof. Y

andre M

aldonado-

37

• No grafo descrito a seguir:

– O menor caminho entre Maringá e Londrina teria comprimento 100;

– Mesmo que houvesse uma aresta ei ligando diretamente as duas cidades com w(ei)>100;

Astorga

LondrinaMaringá

Mandaguari

50

6535

70

120

GRAFOS

Prof. Y

andre M

aldonado-

38

GRAFOS

• Exemplo:– Aplicação do algoritmo de Dijkstra para

encontrar menor distância entre cidades.

UMUARAMA

PARANAVAÍ

LONDRINA

APUCARANA

MARINGÁ

CIANORTE

CAMPO MOURÃO

50

90

60

9080

100

70

75

140

80

CORNÉLIO PROCÓPIO

60

∞

∞

∞

∞

∞∞

∞∞

170

Prof. Y

andre M

aldonado-

39

• Encontrar a menor distância entre UMUARAMA e outra cidade:– Serão utilizados três vetores:

UMUPVIMGALDACPRCNECMOAPUS

∞∞∞∞∞∞∞∞D

--------P

GRAFOS

S – conjunto com todos os vértices do grafo, inicialmente todos devemser checados. Na medida em que forem checados serão marcados comsombreamento.

D – distância entre cada vértice e a origem do caminho. Inicialmente infinita.

P – lista dos predecessores de cada vértice no caminho mais curto.Inicialmente vazia.

Prof. Y

andre M

aldonado-

40

• Encontrar a menor distância entre UMUARAMA e outra cidade:

0140∞∞∞80170∞D

UMUARAMA

PARANAVAÍ

LONDRINA

APUCARANA

MARINGÁ

CIANORTE

CAMPO MOURÃO

50

90

60

9080

100

70

75

140

80

CORNÉLIO PROCÓPIO

60

80

170

0

140

∞∞

∞∞

170

#UMU---UMUUMU-P

Primeiro passo:-Marca-se o vértice de origem vo como checado;-A sua distância éconsiderada zero;-Coloca-se no vetor de distâncias as distâncias entre vo e os seus adjacentes.

UMUPVIMGALDACPRCNECMOAPUS

GRAFOS

Prof. Y

andre M

aldonado-

41

• Encontrar a menor distância entre UMUARAMA e outra cidade:

0140155∞∞80160∞D

UMUARAMA

PARANAVAÍ

LONDRINA

APUCARANA

MARINGÁ

CIANORTE

CAMPO MOURÃO

50

90

60

9080

100

70

75

140

80

CORNÉLIO PROCÓPIO

60

80

160

0

140

155∞

∞∞

170

#UMUCNE--UMUCNE-P

Repetir:-Marca-se o vértice com menor D[u] como checado.-Identifica-se em P o seu predecessor.-Atualiza-se D[v] para todo v adjacente àalgum u já checado.Até que todos os vértices sejam checados.

UMUPVIMGALDACPRCNECMOAPUS

“RELAXAMENTO”se D[u]+w(u,z) < D[z] então

D[z] ← D[u]+w(u,z);

GRAFOS

Prof. Y

andre M

aldonado-

42

• Encontrar a menor distância entre UMUARAMA e outra cidade:

0140155∞∞80160∞D

UMUARAMA

PARANAVAÍ

LONDRINA

APUCARANA

MARINGÁ

CIANORTE

CAMPO MOURÃO

50

90

60

9080

100

70

75

140

80

CORNÉLIO PROCÓPIO

60

80

160

0

140

155∞

∞∞

170

#UMUCNE--UMUCNE-P

UMUPVIMGALDACPRCNECMOAPUS

GRAFOS

Prof. Y

andre M

aldonado-

43

• Encontrar a menor distância entre UMUARAMA e outra cidade:

0140155245∞80160215D

UMUARAMA

PARANAVAÍ

LONDRINA

APUCARANA

MARINGÁ

CIANORTE

CAMPO MOURÃO

50

90

60

9080

100

70

75

140

80

CORNÉLIO PROCÓPIO

60

80

160

0

140

155215

245∞

170

#UMUCNEMGA-UMUCNEMGAP

UMUPVIMGALDACPRCNECMOAPUS

GRAFOS

Prof. Y

andre M

aldonado-

44

• Encontrar a menor distância entre UMUARAMA e outra cidade:

0140155245∞80160215D

UMUARAMA

PARANAVAÍ

LONDRINA

APUCARANA

MARINGÁ

CIANORTE

CAMPO MOURÃO

50

90

60

9080

100

70

75

140

80

CORNÉLIO PROCÓPIO

60

80

160

0

140

155215

245∞

170

#UMUCNEMGA-UMUCNEMGAP

UMUPVIMGALDACPRCNECMOAPUS

GRAFOS

Prof. Y

andre M

aldonado-

45

• Encontrar a menor distância entre UMUARAMA e outra cidade:

0140155245∞80160215D

UMUARAMA

PARANAVAÍ

LONDRINA

APUCARANA

MARINGÁ

CIANORTE

CAMPO MOURÃO

50

90

60

9080

100

70

75

140

80

CORNÉLIO PROCÓPIO

60

80

160

0

140

155215

245∞

170

#UMUCNEMGA-UMUCNEMGAP

UMUPVIMGALDACPRCNECMOAPUS

GRAFOS

Prof. Y

andre M

aldonado-

46

• Encontrar a menor distância entre UMUARAMA e outra cidade:

014015524530580160215D

UMUARAMA

PARANAVAÍ

LONDRINA

APUCARANA

MARINGÁ

CIANORTE

CAMPO MOURÃO

50

90

60

9080

100

70

75

140

80

CORNÉLIO PROCÓPIO

60

80

160

0

140

155215

245305

170

#UMUCNEMGALDAUMUCNEMGAP

UMUPVIMGALDACPRCNECMOAPUS

GRAFOS

Prof. Y

andre M

aldonado-

47

• Encontrar a menor distância entre UMUARAMA e outra cidade:

014015524530580160215D

UMUARAMA

PARANAVAÍ

LONDRINA

APUCARANA

MARINGÁ

CIANORTE

CAMPO MOURÃO

50

90

60

9080

100

70

75

140

80

CORNÉLIO PROCÓPIO

60

80

160

0

140

155215

245305

170

#UMUCNEMGALDAUMUCNEMGAP

UMUPVIMGALDACPRCNECMOAPUS

Todos os vértices já checados: FIM.

GRAFOS

Prof. Y

andre M

aldonado-

48

• Encontrar a menor distância entre UMUARAMA e outra cidade:– Interpretando os resultados:

• O vetor D tem as menores distâncias desde Umuarama;• Retrocedendo nos predecessores a partir de um vértice de

forma encadeada, obtêm-se a seqüência invertida do caminho.• Exemplo: caminho de UMU até CPR:

014015524530580160215D

#UMUCNEMGALDAUMUCNEMGAP

UMUPVIMGALDACPRCNECMOAPUS

CPR – LDA – MGA – CNE - UMU

UMU – CNE – MGA – LDA - CPR

GRAFOS

Prof. Y

andre M

aldonado-

49

GRAFOS

• O algoritmo de Dijkstra:

– Entrada: um grafo G ponderado, conexo e sem pesos negativos; um vértice v de G (vértice de origem).

– Saída: menores distâncias a partir de v, incluindo os seus caminhos;

– D[v] ← 0;– v é visitado;– Enquanto houver algum vértice em S ainda não visitado faça

• Marque, entre os adjacentes dos vértices checados, o vértice u com menor valor D[u] que ainda não foi checado;

• Coloque em P o predecessor de u;• Para cada vértice z adjacente a u faça

Se D[u]+w((u,z))<D[z] então // relaxamentoD[z] ← D[u]+w((u,z));

– Retorne os vetores D e P.

Prof. Y

andre M

aldonado-

50

GRAFOS

• Exercício:– Dado o seguinte grafo, mostre a seqüência

de evolução dos valores dos vetores D, P e S ao se executar o algoritmo de Dijkstraconsiderando “Cornélio Procópio” como vértice de origem.

UMUARAMA

PARANAVAÍ

LONDRINA

APUCARANA

MARINGÁ

CIANORTE

CAMPO MOURÃO

50

90

60

9080

100

70

75

140

80

CORNÉLIO PROCÓPIO

60

170

Prof. Y

andre M

aldonado-

51

Bibliografia

• Ziviani, Nivio. Projeto de Algoritmos – com implementações em Java e C++. Editora Thomson, 2007;

• Tenenbaum, Langsam e Augenstein. Estruturas de Dados Usando C. Editora Makron Books, 1995;

• Moraes, Celso Roberto. Estruturas de Dados e Algoritmos. Editora Berkley, 2001;

• Goodrich e Tamassia. Projeto de Algoritmos. Editora Bookman, 2002.