1

GrafosMsc. Daniele Carvalho Oliveira

2

Pontes de Königsberg (1736)

3

O que são Grafos Conjunto de pontos e linhas que conectam os

pontos.

Grafo é um modelo matemático que representa relações entre objetos.

4

O que são Grafos Grafos são estruturas de dados largamente

usadas em computação.

Exemplos de aplicações são: Modelagem de circuitos digitais Representação de processos em sistemas

paralelos ou distribuídos, Redes Redes Sociais Recuperação de Informação

5

O que são Grafos Similar a árvores e listas, com menos

restrições

6

7

Definição Um Grafo é um par ordenado

é um conjunto finito não-vazio. Os elementos de são denominados vértices.

é um conjunto finito de pares ordenados de vértices. Os elementos de são denominados arestas. Dois vértices ligados por uma aresta são

denominados adjacentes

8

Exemplo

1

2 0

3

4

9

Conceitos de Grafos

10

Laços, Arestas Múltiplas e Multigrafo

11

Grafo Trivial e Grafo Simples

A B C

12

Grafo Completo

13

Grafo Regular

Não é Grafo Regular Grafo Regular de grau 3

1

2 0

3

4

14

Subgrafo

1

2 0

3

43

4

1

3

4

0

15

Caminho simples, trajeto e ciclos

Um Caminho é uma sequência de vértices , tal que

Quando todos os vértices do caminho são distintos, recebe o nome de caminho simples.

Quando todas as arestas são distintas, o caminho recebe o nome de trajeto

Um ciclo é um caminho , tal que e

16

Caminho simples:

Trajeto:

Ciclo:

1

2 0

3

4

17

Grafo Conexo e Desconexo

1

2 0

3

4

2

3 4

1

18

Grafo Ponderado

C

F E

B

DA

5

7

3

2

4

8

1

6

19

Dígrafo

1

2

3

5

6

4

20

Dígrafo Grafo Orientado

Deve-se respeitar a orientação das arestas

21

Dígrafo Grau de entrada: número de arestas que

incidem no vértice Vértice Fonte: grau de entrada = 0

Grau de saída: número de arestas que partem do vértice Vértice Sumidouro: grau de saída = 0

22

Árvores Um Grafo

Não possui ciclos Conexo Seja , se possui grau menor ou igual a 1, então

é uma folha Uma árvore com vértices possui arestas. Um grafo é uma árvore, se, e somente se, existir

um único caminho entre cada par de vértices de .

23

24

Representação de Grafos

25

Como representar grafos em nossos algoritmos?

Estruturas de dados! Matrizes

Matriz de Adjacência Matriz de Incidência

Listas Listas de Adjacência

26

Matriz de Adjacência Dado um grafo Uma Matriz de Adjacência é formada por

linhas e colunas = número de vértices do grafo

27

1 2 3 4 5

1 0 1 0 0 1

2 1 0 1 1 0

3 0 1 0 1 0

4 0 1 1 0 1

5 1 0 0 1 1

1

5 2

34

Simétrica

28

1 2 3 4 5

1 0 1 0 0 1

2 0 0 1 0 0

3 0 1 0 0 0

4 0 1 1 0 0

5 0 0 0 1 1

1

5 2

34

29

Matriz de Adjacência O espaço reservado para armazenar as

informações da matriz é da ordem Para buscar uma aresta:

30

Matriz de Incidência Dado um grafo de vértices e arestas

31

e1

e2

e3

e4

e5

e6

e7

e8

1 1 0 0 0 0 0 1 0

2 1 1 1 0 1 0 0 0

3 0 1 1 1 0 0 0 0

4 0 0 0 1 1 1 0 0

5 0 0 0 0 0 1 1 0

1

5 2

34 e4

e2 e3

e1

e5e6

e7e8

32

33

e1

e2

e3

e4

e5

e6

e7

e8

1 1 0 0 0 0 0 1 0

2 -1 1 -1 0 -1 0 0 0

3 0 -1 1 -1 0 0 0 0

4 0 0 0 1 1 -1 0 0

5 0 0 0 0 0 1 -1 0e4

e2 e3

e1

e5e6

e7e8 1

5 2

34

34

Matriz de Incidência O espaço reservado para armazenar as

informações da matriz é da ordem Para buscar uma aresta:

35

Lista de Adjacência Consiste em um vetor com entradas Cada entrada possui uma lista encadeada de

vértices adjacentes à .

36

1

5 2

34

1

2

3

4

5

5 2

1

2

5

1

4

4

2

4

3

3

37

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

38

Matriz de Incidência O espaço reservado para armazenar as

informações da matriz é da ordem Para buscar uma aresta:

Para descobrir se existe a aresta deve-se percorrer a lista do nó até encontrar (ou não)

39

Busca em Grafos

40

Algoritmos de Busca Operação mais comum em Grafos

Visita sistemática a seus nós (uma única vez!) Similar às buscas em árvore

Para passear ou caminhar pelos vértices e arestas, utiliza-se marcar um vértice quando ele já foi visitado.

41

Algoritmos de Busca Dois tipos básicos de busca

Busca em Profundidade Busca em Largura

42

Busca em Profundidade

43

1

5 2

34

1

2

3

4

5

5 2

1

2

5

1

4

4

2

4

3

3

44

Busca em Profundidade Para acessar todos os vértices do grafo, a

busca em profundidade varre a lista de adjacência de cada vértice do grafo Assim, o tempo gasto para a operação é

45

Busca em Largura

46

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

1Fila

1 2 3 4 5

∞ ∞ ∞ ∞ ∞Distâncias

47

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

Fila

1 2 3 4 5

0 ∞ ∞ ∞ ∞Distâncias

48

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

5 2Fila

1 2 3 4 5

0 1 ∞ ∞ 1Distâncias

49

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

2Fila

1 2 3 4 5

0 1 ∞ ∞ 1Distâncias

50

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

2Fila

1 2 3 4 5

0 1 ∞ ∞ 1Distâncias

51

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

2 4Fila

1 2 3 4 5

0 1 ∞ 2 1Distâncias

52

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

4Fila

1 2 3 4 5

0 1 ∞ 2 1Distâncias

53

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

4Fila

1 2 3 4 5

0 1 ∞ 2 1Distâncias

54

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

4 3Fila

1 2 3 4 5

0 1 2 2 1Distâncias

55

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

3Fila

1 2 3 4 5

0 1 2 2 1Distâncias

56

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

3Fila

1 2 3 4 5

0 1 2 2 1Distâncias

57

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

Fila

1 2 3 4 5

0 1 2 2 1Distâncias

58

1

2

3

4

5

5 2

3

2

2

4

3

1

5 2

34

Fila

1 2 3 4 5

0 1 2 2 1Distâncias

59

Busca em Largura Primeiro os vértices são inicializados, ou seja,

marcados como não visitados. O vetor de distâncias é inicializado com ∞ em

todas as posições Este processo de inicialização gasta tempo

60

Busca em Largura A medida que os vértices são encontrados, são

colocados em uma fila As operações de inserção e remoção da fila

gastam tempo Como todos os vértices são colocados e retirados

da fila, o tempo total é

61

Busca em Largura Como cada vértice é colocado na fila apenas 1

vez, a lista de adjacência de cada um só é analisado 1 vez Tempo

Portanto o tempo de execução da busca em largura é