Grafos

GRAFOS
Grafos – São estruturas de dados bem parecidas com árvores.
Exemplo:
J

I
E
G

D

F
A

H

B

C

Adjacência – Dois nós são ditos adjacentes um do outro, se forem conectados por uma única aresta.
Exemplo:
Nós adjacentes: I e G, I e H, I e J, H e G, H e B, D e C, etc.
Caminhos – Um caminho é uma seqüência de arestas.
Exemplo:
O caminho do nó B para o nó J que passa pelos nós A e E
Resposta: BAEJ
Pode haver mais de um caminho entre dois nós
Resposta: Outro caminho : BCDJ
Grafos conectados e não conectados – Um grafo é dito conectado, se houver pelos menos um caminho de cada nó para cada outro nó.
Exemplos:
B
B
D
A

D
C
Grafo conectado

A
C
Grafo não conectado

1

Grafos Não orientados –
B
C

A

Grafos Orientados –
Exemplo:
Representação de uma rua de mão única através de um grafo. A direção só é permitida em uma única direção.
B
C

A

Grafos Ponderados – São tipos de grafos que podem representar:
- a distância física entre dois nós;
- o tempo que leva para ir de um nó ao outro
- ou quanto custa viajar de um nó ao outro.

Busca em Profundidade
Exemplo:

3

H

7

8

G

B

4

F

2

I

1
5

A

C
6
D

E
9

2

Busca em Largura.
Exemplo:

6
B

8

F

2

H

1
A

3
C
4

7
G

D

9
I

E
5

Bibliografia:
LAFORE, Robert. Estruturas de dados & Algoritmos em Java. Rio de Janeiro: Ciência Moderna, 2004.

3