© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados Grafos IF672 - Algoritmos e Estruturas de Dados CIn - UFPE Adriana Libório

© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados

Grafos

IF672 - Algoritmos e Estruturas de Dados CIn - UFPE

Adriana Libório Fernandes LinsArthur Cavalcanti AlemÁtila Valgueiro Malta MoreiraFlavio Juvenal da Silva JúniorGustavo Cauê Silva BotelhoMatheus Bispo Arrais de Souza

Murilo Raphael de Souza LiraRafael Alberto Gomes Pereira LimaRafael Brandão LoboRafael Loureiro de CarvalhoTiago Carneiro Pessoa CantoVinicius Miranda Cesar

[email protected]


GrafosUm Grafo é uma estrutura de dados que representa objetos e as relações entre eles. Pode ser usado para:-Representar redes de computadores;-Encontrar a menor distância entre duas cidades;-Representar os estados de uma máquina de estados...Entre várias outras coisas.


GrafosGrafos são formados por vértices (ou nós) e arestas, que ligam os vértices:

Rec

SP

Salv

RJ

Ex: Rotas de Avião Ex: Computadores conectados

g6c19

g6c20

g6c21

Servidor

Cidades (vértices)

Rec

SP

Salv

RJ

Rotas (arestas) Conexões (arestas)Computadores (vértices)

g6c19

g6c20

g6c21

Servidor


ArestasHá dois tipos de arestas, segundo sua orientação:• Direcionadas (mão única), tais que (v,w) (w,v)

v w v w

v wv w v w

origem destino origemdestino

• Não-direcionadas (mão dupla), tais que (v,w) = (w,v)origemdestino

origem destino


Grafos DirecionadosCada aresta tem um sentido único, partindo do vértice de origem e chegando ao vértice de destino:

1

3 67

2 9 5

Ex: Ruas de uma cidade Ex: Árvore (arestas pai-filho)


Grafos Não-DirecionadosTodas as arestas são de mão dupla, ou seja, não importa o sentido escolhido, e (v,w) = (w,v):


Representando GrafosHá várias formas de representar um grafo. As mais comuns são:• Matriz de Adjacências

- Relação entre pares: se dois vértices são vizinhos- Espaço fixo: desperdício

• Lista de Incidências- Lista ligada de vizinhos de cada vértice- Acesso seqüencial: ideal para buscas


Matriz de AdjacênciasPara cada par, 1 se são vizinhos, 0 em caso contrário.São necessárias n² posições:

0

0110100

1001010

1000110

0100101

1011000

0110000

0001000

0123456

0 1 2 3 4 5 60 1 1 0 1 0 0

2 4

0

3

1

6

5

Uma linha inteira para cada vértice


Lista de IncidênciasPara cada vértice, uma lista contendo apenas os vértices ligados a ele:

1

0

0

1

0

1

3

0

1

2

3

4

5

6

2

3

4

4

2

2

4

5

5

6

3

2 4

0

3

1

6

5

10 2 4

0


Lista de IncidênciasImplementação:

class Grafo {

Lista[] adj;

public Grafo(int n) { adj = new Lista[n]; for (int i = 0; i < n; i++) adj[i] = new Lista(); }

}


Arestas com PesoHá outra classificação para arestas:• Arestas sem peso, com custo uniforme

1 2

3

• Arestas com peso Ex: distâncias

4

1 2

3 4

30

2245

36

Dois vértices são vizinhos? Se são, qual o custo da ligação?


Grafos com PesosCada aresta tem um custo (peso) associado a ela. Ex: Mapa de uma cidade

A

C

B

D

E

20 km

15 km 12 km

13 km30 km28 km

Arestas inexistentes são arestas com custo infinito. km

km


Matriz de Adjacências com PesosPara cada par, o custo da aresta se são vizinhos, infinito em caso contrário:

832

843

314

473

217

34

3

0123456

0 1 2 3 4 5 6

2 4

0

3

1

6

5

4

3

3 8

3

1

27

4


Lista de Incidências com PesosCada nó da lista contém o vértice vizinho e o custo da aresta (sem infinitos):

2 4

0

3

1

6

5

4

3

3 8

3

1

27

4

0

1

2

3

4

5

6

1

0

0

1

0

1

3

8

8

3

4

2

3

3

2

3

4

4

2

2

3

4

1

7

1

4

4

5

5

6

3

2

3

4

3

7

V C V C V C


Lista de Incidências com PesosImplementação:

class NoLista { int vertice int custo; NoLista prox;}

A única modificação ocorre na representação das arestas, ou seja, nos nós da lista de incidências. Neles, uma nova informação (o custo) deve ser armazenada.

Nova informação

Documents

© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados Grafos IF672 - Algoritmos e Estruturas de Dados CIn - UFPE Adriana Libório