As Estruturas de Dados e Algoritmos

FACENS – Faculdade de Engenharia de Sorocaba

Engenharia da Computação – Estruturas de Dados e Algoritmos

Prof.: Fábio Lopes Caversan

Lista de Exercícios – Grafos

1.Considere o grafo abaixo:

[pic 1]

É solicitado o seguinte:

• Todos os caminhos não cíclicos de a até h

A > C > D > H

A > C > F > H

A > G > F > H

A > G > F > C > D > H

A > B > E > G > F > C > D > H

A > B > E > G > F > H

• Todos os caminhos não cíclicos de c até e

C > A > B > E

C > A > G > E

C > F > G > E

C > D > H > F > G > E

C > D > H > F > G > A > B > E

• Todos os caminhos não cíclicos de b até f

B > A > C > F

B > A > C > D > H > F

B > E > G > F

B > E > G > A > C > F

B > E > G > A > C > D > H > F

2. Ainda considerando a figura do exercício 1, ache os todos os nós adjacentes para os nós a, f, g.

A => B, C, G

F => C, G, H

G => A, E, F

3. Dê o resultado do passeio com o algoritmo de profundidade (depth-first) sobre o gráfico do exercício 1, iniciando do vértice A

A > G > E > B > F > C > D > H

4. Dê o resultado do passeio com o algoritmo de largura  (breadth-first) sobre o gráfico do exercício 1, iniciando do vértice A

A > B > C > G > E > F > D > H

5. Desenhe a matriz de adjacência do grafo do exercício 1

	A	B	C	D	E	F	G	H
A	0	1	1	0	0	0	1	0
B	1	0	0	0	1	0	0	0
C	1	0	0	1	0	1	0	0
D	0	0	1	0	0	0	0	1
E	0	1	0	0	0	0	1	0
F	0	0	1	0	0	0	1	1
G	1	0	0	0	1	1	0	0
H	0	0	0	1	0	1	0	0

6. Desenhe a lista de adjacência do grafo do exercício 1

[pic 2]

---

7. Ache o caminho mais curto entre o nó A e todos os outros nós do grafo abaixo:

[pic 3]

A até B => A > B = 4

A até C => A > C = 3

A até D => A > C > D = 11

A até E => A > B > E = 7 ou A > G > E = 7

A até F => A > G > F = 3

A até G => A > G = 1

A até H => A > G > F > H = 10

8. Dê a matriz adjacência do grafo do exercício 7

	A	B	C	D	E	F	G	H
A	0	4	3	0	0	0	1	0
B	4	0	0	0	3	0	0	0
C	3	0	0	8	0	5	0	0
D	0	0	8	0	0	0	0	5
E	0	3	0	0	0	0	6	0
F	0	0	5	0	0	0	2	7
G	1	0	0	0	6	2	0	0
H	0	0	0	5	0	7	0	0

...