Aula de redes 3

1Aula 03 Busca em largura

BC0506 - Comunicao e Redes

David Correa Martins [email protected]

2Roteiro da aula

Grafos- Definies e Propriedades

Algoritmos de buscas em grafos- Busca em largura

Lista 1

Atividade prtica

3I. Definies

4Definies

Um caminho do vrtice s ao vrtice t uma sequncia de vrtices , onde cada par de vrtices consecutivos conectado por uma aresta.

Um caminho de s a t um caminho mnimo se ele tem comprimento mnimo.

2

1 3

4

5

6

7

um caminho de 1 a 4.

um caminho mnimo de 1 a 4.

5Definies

A distncia entre s a t o comprimento do caminho mnimo entre os dois vrtices.

A distncia entre 4 e 5 2.



A distncia entre 4 e 8 ?.

2

1 3

4

5

6

7

8

6Definies

Dizemos que um vrtice t alcanvel a partir de um vrtice s, se existe um caminho de s a t.

Se t no alcanvel a partir de s, ento dizemos que a distncia entre esses vrtices infinita.

O dimetro definido como a maior distncia entre os possveis pares alcanveis de vrtices

A distncia entre 4 e 8 infinita2

1 3

4

5

6

7

8

7Definies

Grafo completo: um grafo no qual dois vrtices distintos quaisquer so adjacentes.

Um grafo completo de ordem=n tem o tamanho=n(n-1)/2

8Definies

O grau de um vrtice o nmero de extremidades de arestas naquele vrtice.

2

1 3

4

5

6

7Vrtices Grau

1 32 43 54 25 26 17 0

9Definies

O grau de entrada (in-degree) o nmero de arestas direcionadas que entram no vrtice.O grau de sada (out-degree) o nmero de arestas direcionadas que saem do vrtice.

2

1 3

4

5

6

7Vrtices in-degree out-degree

1 1 02 1 13 3 24 1 15 0 16 1 27 0 0

10

Definies

Um subgrafo consiste em um conjunto de vrtices e um conjunto de arestas que so subconjuntos do conjunto original de vrtices e arestas, respectivamente.

2

1 3

4

5

6

7

Subgrafo

2

1 3

5

Um subgrafo um grafo obtido apagando-se parte do grafo original e deixando o resto sem modificaes.

11

Definies

Uma componente conexa de um grafo G um subgrafo de G que , ao mesmo tempo, conexo e no subgrafo de nenhum subgrafo maior conexo.

2

1 3

4

5

6

7

1 componente conexo

2

1 5

4

6

8

3

7

8

12

Definies

Uma componente conexa de um grafo G um subgrafo de G que , ao mesmo tempo, conexo e no subgrafo de nenhum subgrafo maior conexo.

2

1 3

4

5

6

7

1 componente conexo

2

1 5

4

6

8

3

7

8

4 componentes conexos

13

Definies

Um grafo planar (i.e., com representao planar) i.e., se ele pode ser desenhado sem cruzamento de arestas.

14

Definies

Um grafo planar (i.e., com representao planar) i.e., se ele pode ser desenhado sem cruzamento de arestas.

15

Definies

L. Euler descobriu que um grafo planar divide o plano em um determinado nmero de regies.

O-T+R = 2R = 2-O+T

O = ordem do grafoT = tamanho do grafo

R = 2-8+12 = 6 R = 2-4+6 = 4

16

Definies

Exerccio: Verifique a frmula de Euler para o grafo planar simples e conexo na figura abaixo.

R = 2-O+T

17

Definies


R = 2-O+T

R = 2-13+19 = 8

18

Definies


R = 2-O+T

R = 2-13+19 = 8

19

Definies


R = 2-O+T

R = 2-13+19 = 8

20

Definies

Apenas 4 cores so necessrias e suficientes para qualquer mapa.

Problema: Colorir um mapa sem que regies com fronteiras comuns tivessem a mesma cor.

21

II. Buscas em grafos(algoritmos de varredura em grafos)

22

Buscas em grafos

Em muitas aplicaes de redes necessrio percorrer rpidamente o grafo, visitando-se todos os vrtices.

Para que isso seja realizado de forma sistemtica e organizada, so utilizados algoritmos de busca em grafos.

As buscas so usadas em diversas aplicaes para determinar informaes relevantes sobre a estrutura do grafo:

- Web crawling- Redes de computadores- Redes sociais- Redes de colaborao acadmica

23

Buscas em grafos

Os algoritmos de busca em grafos permitem percorrer o grafo buscando todos os vrtices que so acessveis a partir de um determinado vrtice em questo.

Existem diversas maneiras de realizar a busca: Cada estratgia se caracteriza pela ordem em que os vrtices so visitados.

So 2 os algoritmos bsicos de buscas em grafos:- Busca em largura.- Busca em profundidade.

24

Busca em largura

Inicialmente partimos de um n s, formando o conjunto {s}.Explorao nvel a nvel (um nvel por vez).Fronteira = nvel atual. Iterativamente avanar a fronteira para o nvel seguinte, cuidando para no voltar ao nvel anterior.

25

Busca em largura


26

Busca em largura


27

Busca em largura


28

Busca em largura


29

Busca em largura

Na busca em largura percorre-se todos os vrtices alcanveis a partir de um vrtice s, em ordem de distncia deste.

Vrtices a mesma distncia podem ser percorridos em qualquer ordem.

Constri uma rvore de busca em largura com raiz em s. Cada caminho de s a um vrtice t corresponde a um caminho mais curto de s a t.

O processo implementadousando uma FILA.

30

Busca em largura

Uma fila uma estrutura de dados que permite armazer uma sequncia de valores mantendo uma determinada ordem:primeiro a entrar, primeiro a sair.

First-In-First-Out (FIFO)

31

Busca em largura

O algoritmo de busca em largura atribui cores a cada vrtice

32

Busca em largura

2

1 3

4

5

6

7

Grafo inicial

33

Busca em largura (origem s=4)

2

1 3

4

5

6

7

Fila = {4}

(0)

Passo 0

34


2

1 3

4

5

6

7

(0)

Passo 2

(1) (1)

Fila = {1,3}

35


2

1 3

4

5

6

7

(0)

Passo 4

(1) (1)

(2)

Fila = {3,2}

36


2

1 3

4

5

6

7

(0)

Passo 6

(1) (1)

(2) (2)

(2)

Fila = {2,6,5}

37


2

1 3

4

5

6

7

(0)

Passo 8

(1) (1)

(2) (2)

(2)

(3)Fila = {6,5,7}

38


2

1 3

4

5

6

7

(0)

Passo 9

(1) (1)

(2) (2)

(2)

(3)Fila = {5,7}

39


2

1 3

4

5

6

7

(0)

Passo 10

(1) (1)

(2) (2)

(2)

(3)Fila = {7}

40


2

1 3

4

5

6

7

(0)

Passo 11

(1) (1)

(2) (2)

(2)

(3)Fila = {}

41

Busca em largura

Como determinamos o caminho exato para: a partir do vrtice 4 chegar ao vrtice 5?

2

1 3

4

5

6

7

(0)

(1) (1)

(2) (2)

(2)

(3)

? ?

42

Busca em largura

2

1 3

4

5

6

7

Grafo inicial

43


2

1 3

4

5

6

7

Fila = {4}

(0)

Passo 0

Predecessores:1: 2:3:4: --5:6:7:

44


2

1 3

4

5

6

7

(0)

Passo 2

(1) (1)

Fila = {1,3}

Predecessores:1: 4 2:3: 44: --5:6:7:

45


2

1 3

4

5

6

7

(0)

Passo 4

(1) (1)

(2)

Fila = {3,2}

Predecessores:1: 4 2: 13: 44: --5:6:7:

46


2

1 3

4

5

6

7

(0)

Passo 6

(1) (1)

(2) (2)

(2)

Fila = {2,6,5}

Predecessores:1: 4 2: 13: 44: --5: 36: 37:

47


2

1 3

4

5

6

7

(0)

Passo 8

(1) (1)

(2) (2)

(2)

(3)Fila = {6,5,7}

Predecessores:1: 4 2: 13: 44: --5: 36: 37: 2

48


2

1 3

4

5

6

7

(0)

Passo 9

(1) (1)

(2) (2)

(2)

(3)Fila = {5,7}

Predecessores:1: 4 2: 13: 44: --5: 36: 37: 2

49


2

1 3

4

5

6

7

(0)

Passo 10

(1) (1)

(2) (2)

(2)

(3)Fila = {7}

Predecessores:1: 4 2: 13: 44: --5: 36: 37: 2

50


2

1 3

4

5

6

7

(0)

Passo 11

(1) (1)

(2) (2)

(2)

(3)Fila = {}

Predecessores:1: 4 2: 13: 44: --5: 36: 37: 2

51


2

1 3

4

5

6

7

(0)

(1) (1)

(2) (2)

(2)

(3)

Predecessores:1: 4 2: 13: 44: --5: 36: 37: 2

Caminho exato para: a partir do vrtice 4 chegar ao vrtice 5?

52


2

1 3

4

5

6

7

(0)

(1) (1)

(2) (2)

(2)

(3)

Predecessores:1: 4 2: 13: 44: --5: 36: 37: 2

Caminho exato para: a partir do vrtice 4 chegar ao vrtice 5?

534

O caminho ser

Para o caminho entre a origem e o destino, parte-se do vrtice de destino at chegar origem. Depois inverte-se o vetor obtido.

53

Busca em largura (Algoritmo)

Constantes:BRANCO , CINZA ,PRETO, INFINITO

Variveis:Q (pilha) , s (vrtice de origem)

Propriedades do vrtice v:v.cor (cor do vrtice)v.dist (distncia do vrtice v at a origem s)v.pre (precedessor do vrtice v)

Funes :Insere(Q,v), permite inserir o vrtice v na fila Q.Remove(Q), permite remover o primeiro vrtice da fila Q.

54


Busca em largura = Breadth First Search (BFS)

BFS(G,s): Para cada vrtice v em G.V-{s} faa v.cor = BRANCO v.dis = INFINITO s.cor = CINZA s.dis = 0 Q = VAZIO Insere(Q,s)

Enquanto Q VAZIO faa u = Remove(Q) Para cada vrtice v em G.Adj[u] faa se v.cor == BRANCO v.cor = CINZA v.dis = u.dis+1 v.pre = u Insere(Q,v) u.cor = PRETO

55


Busca em largura = Breadth First Search (BFS)

BFS(G,s): Para cada vrtice v em G.V-{s} faa v.cor = BRANCO v.dis = INFINITO s.cor = CINZA s.dis = 0 Q = VAZIO Insere(Q,s)


Inicializao

Percorre o grafo

Explora os vizinhos de u

56


Para cada vrtice v em G.V-{s} faa v.cor = BRANCO v.dis = INFINITO s.cor = CINZA s.dis = 0 Q = VAZIO Insere(Q,s)

sr t u

wv x z

Inicializao

57


Para cada vrtice v em G.V-{s} faa v.cor = BRANCO v.dis = INFINITO s.cor = CINZA s.dis = 0 Q = VAZIO Insere(Q,s)

sr t u

wv x z

(Inf)

(Inf)

(Inf) (Inf)

(Inf)

(Inf)

(Inf)

Q = {s}(0)

Inicializao

58


sr t u

wv x z

(Inf)

(Inf)

(Inf) (Inf)

(Inf)

(Inf)

(Inf)

Q = {s}


Percorre o grafo


(0)

59


sr t u

wv x z

(Inf)

(Inf)

(Inf) (Inf)

(Inf)

(1,s)

(1,s)

Q = {w,r}

u = s

(0)


Percorre o grafo


60


sr t u

wv x z

(Inf)

(Inf)

(Inf) (Inf)

(Inf)

(1,s)

(1,s)

Q = {r}

u = w

(0)


Percorre o grafo


61


sr t u

wv x z

(2,w)

(2,w)

(Inf) (Inf)

(Inf)

(1,s)

(1,s)

Q = {r,t,x}

u = w

(0)


Percorre o grafo


62


sr t u

wv x z

(2,w)

(2,w)

(Inf) (Inf)

(Inf)

(1,s)

(1,s)

Q = {t,x}

u = r

(0)


Percorre o grafo


63


sr t u

wv x z

(2,w)

(2,w)

(2,r) (Inf)

(Inf)

(1,s)

(1,s)

Q = {t,x,v}

u = r

(0)


Percorre o grafo


64


sr t u

wv x z

(2,w)

(2,w)

(2,r) (Inf)

(Inf)

(1,s)

(1,s)

Q = {x,v}

u = t

(0)


Percorre o grafo


65


sr t u

wv x z

(2,w)

(2,w)

(2,r) (Inf)

(3,t)

(1,s)

(1,s)

Q = {x,v,u}

u = t

(0)


Percorre o grafo


66


sr t u

wv x z

Q = {v,u}

u = x


Percorre o grafo


(2,w)

(2,w)

(2,r) (Inf)

(3,t)

(1,s)

(1,s) (0)

67


sr t u

wv x z

Q = {v,u,z}

u = x


Percorre o grafo


(2,w)

(2,w)

(2,r) (3,x)

(3,t)

(1,s)

(1,s) (0)

68


sr t u

wv x z

Q = {u,z}

u = v


Percorre o grafo


(2,w)

(2,w)

(2,r) (3,x)

(3,t)

(1,s)

(1,s) (0)

69


sr t u

wv x z

Q = {z}

u = u


Percorre o grafo


(2,w)

(2,w)

(2,r) (3,x)

(3,t)

(1,s)

(1,s) (0)

70


sr t u

wv x z

Q = {z}

u = u


Percorre o grafo


(2,w)

(2,w)

(2,r) (3,x)

(3,t)

(1,s)

(1,s) (0)

71


sr t u

wv x z

Q = {}

u = z


Percorre o grafo


(2,w)

(2,w)

(2,r) (3,x)

(3,t)

(1,s)

(1,s) (0)

72


sr t u

wv x z

Q = {}

u = z


Percorre o grafo


(2,w)

(2,w)

(2,r) (3,x)

(3,t)

(1,s)

(1,s) (0)

73

Busca em largura

sr t u

wv x z

Caminho mnimo do vrtice s ao vrtice u:u.pre = tt.pre = ww.pre = s

Assim :

(2,w)

(2,w)

(2,r) (3,x)

(3,t)

(1,s)

(1,s) (0)

74

Busca em largura

O algoritmo de busca em grafos tambm trabalha com grafos no conexos.

Para tais casos, apenas os vrtices v que esto na mesma componente do vrtice s tero valores v.dis INFINITO.

Podemos usar o atributo v.dis de todos os vrtices para decidir se o grafo conexo.

75

III. Sobre a Lista 1

76

Lista 1Dentro do pacote lista1.zip em Repositrio->Listas->Lista 1 no Tidia, considere o seguinte grafo:

Considere o seguinte grafo:RA-lista1.pdf onde RA seu registro acadmico (Tidia, Repositrio-> Listas)

Questes:(1) Calcule a ordem do grafo. [0,5 ponto](2) Calcule o tamanho do grafo. [0,5 ponto](3) Calcule o nmero de componentes conexas do grafo. [1 ponto](4) Existe caminho Euleriano no grafo? (sim/no) [1 ponto](5) Calcule o grau mdio do grafo. [2 pontos](6) Calcule o dimetro do grafo. [2 pontos](7) Aplique o algoritmo de busca em largura para obter a distncia entre o vrtice 1 e 10. [1 ponto](8) Aplique o algoritmo de busca em largura para obter a distncia entre o vrtice 1 e 15. [1 ponto](9) Aplique o algoritmo de busca em largura para obter a distncia entre o vrtice 1 e 20. [1 ponto]

77

Lista 1

78

Lista 1

Submisso:Envie as respostas atravs do seguinte formulrio:https://docs.google.com/forms/d/1tMqosyV9Gtp722Oaz5c-CfPTLyvDKr9ayDEQqQQJLCE/viewform?usp=send_form

Observaes:

No caso da resposta ser um nmero real considere at a segunda casa decimal

(exemplo: 1.66)Pode submeter inmeras vezes, apenas a ltima submisso ser avaliada.Data limite: 9 de junho s 23:59

79

IV. Atividade Prtica

80

Atividade Prtica

Calcule as seguintes informaes do grafo:(1) Nmero de componentes conexas.(2) Ordem e tamanho da maior componente conexa.(3) Ordem e tamanho da menor componente conexa.(4) Grau dos vrtices: a, k, q.

gf h k

pn q r

b c d

m

ea

81

Atividade Prtica

(5) Nmero de regies do grafo planar formado pela maior componente conexa.(6) Utilize o algoritmo de busca em largura para obter a distncia:

(6.1) Do vrtice a ao vrtice q.(6.2) Do vrtice c ao vrtice q.

gf h k

pn q r

b c d

m

ea

82

Atividade Prtica

Calcule as seguintes informaes do grafo:

(1) Nmero de componentes conexas (3).

(2) Ordem e tamanho da maior componente conexa (11, 14).

(3) Ordem e tamanho da menor componente conexa (1, 0).

(4) Grau dos vrtices: a (0), k (5), q (4).

(5) Nmero de regies do grafo planar formado pela maior componente conexa (R = 2-O+T = 5).

83

Atividade Prtica

(6) Utilize o algoritmo de busca em largura para obter a distncia:

(6.1) Do vrtice a ao vrtice q.

gf h k

pn q r

b c d

m

ea

(0)

(Inf) (Inf) (Inf) (Inf)

(Inf) (Inf) (Inf) (Inf)

(Inf) (Inf)

(Inf)

(Inf)

(Inf)

84

Atividade Prtica

(6) Utilize o algoritmo de busca em largura para obter a distncia:

(6.2) Do vrtice c ao vrtice q.

gf h k

pn q r

b c d

m

ea(1,c) (0) (Inf) (Inf)

(3,f) (3,g) (3,g) (3,k)

(2,b) (2,h)

(1,c)

(2,h)

(4,n)

(Inf)

85

Para finalizar...

Como verificar se o grafo no-conexo?

Como saber quais vrtices so alcanveis a partir de c?

gf h k

pn q r

b c d

m

ea(1,c) (0) (Inf) (Inf)

(3,f) (3,g) (3,g) (3,k)

(2,b) (2,h)

(1,c)

(2,h)

(4,n)

(Inf)

86

Para finalizar...

Como verificar se o grafo no-conexo?Examinando o atributo v.dist. Se pelo menos um deles for igual a INFINITO, o grafo no conexo. Caso contrrio, conexo.

Como saber quais vrtices so alcanveis a partir de c?Examinando o atributo v.dist. O vrtice v alcanvel se v.dist INFINITO.

gf h k

pn q r

b c d

m

ea(1,c) (0) (Inf) (Inf)

(3,f) (3,g) (3,g) (3,k)

(2,b) (2,h)

(1,c)

(2,h)

(4,n)

(Inf)

First Slide ExampleSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85Slide 86

Documents

Aula de redes 3