Instituto Superior de Engenharia do Porto
Aula Prática
Estruturas de Informação
Grafos
Representação - Matriz de Adjacências
ficha nº 7
1. Analise com atenção a definição da classe Matriz de Adjacencias de um Grafo
(MatAdjPDig.h) que contem a implementação de uma estrutura do tipo grafo representada
numa matriz.
Adicione à referida classe os seguintes métodos:
a) Verificar se há caminho entre dois vértices. Usar o algoritmo de Warshall.
b) Contar o número de caminhos entre dois vértices.
c) Visualizar um só caminho entre dois vértices (o primeiro que encontrar).
d) Visualizar todos os caminhos entre dois vértices.
e) Visualizar o caminho mínimo entre dois vértices e o respectivo valor. Usar um processo
exaustivo, isto é, que analise todos os caminhos entre esses vértices.
Grafo para Teste
Matriz de Adjacências1 (M)
V.
3
0
1
2
3
4
5
0
0
1
1
0
0
0
O
1
0
0
0
1
1
0
R
2
0
0
0
0
1
1
3
0
0
0
0
0
0
E
4
0
0
0
0
0
1
M
5
0
0
0
0
0
0
1
0
4
2
V.
I
5
1
DESTINO
G
Matriz de Adjacências indica se existe caminho (de comprimento 1) entre dois vértices do grafo.
1