Esercizio 1
Un grafo orientato è una struttura formata da un insieme di nodi e da un
insieme di archi che collegano fra di loro i nodi. Se esiste un arco
da un nodo a ad un nodo b si dice che b è direttamente raggiungibile
da a; perchè a sia direttamente raggiungibile da b deve esistere un
altro arco da b ad a.
Si consideri una rappresentazione di un grafo orientato avente dieci
nodi (identificati da numeri da 0 a 9) costituita da un documento di
testo formato da dieci righe che specificano, per ogni nodo
da 0 a 9, quali altri nodi sono da lui raggiungibili direttamente
percorrendo un arco.
Ad esempio il documento:
1 4 8
3
5 7 2
9 5 4
2 6 7
1 2 0
2
9 8
5 2 6
rappresenta un grafo in cui esistono degli archi dal nodo 0 ai nodi 1, 4 e
8, altri dal nodo 3 ai nodi 4, 5 e 9, in cui il nodo 8 non è collegato
a nessun altro nodo e così via.
Scrivere un programma che prenda da linea di comando tre parametri: un nome
di file (che conterrà una rappresentazione di un grafo come visto in
precedenza) e due numeri interi da 0 a 9 che contraddistingueranno il
nodo di partenza e il nodo di arrivo.
Il programma dovrà verificare se esiste una sequenza di archi che metta
in contatto il nodo di partenza con il nodo di arrivo ed eventualmente
visualizzi la sequenza di nodi che compongono il cammino.
Consigli: diverse
strategie possono essere utilizzate ma in generale il programma
dovrà eseguire una serie di passi nei quali determinare di volta in volta
se fra i nodi direttamente raggiungibili da un insieme di nodi P c'è il
nodo di arrivo. L'insieme P sarà inizialmente formato dal solo nodo di
partenza, poi da tutti
i nodi raggiungibili dal nodo di partenza e così via.
Possono anche essere utilizzate strutture dati diverse ma l'uso di un
vettore di dieci oggetti di tipo ArrayList (o Vector) per memorizzare
i nodi raggiungibili da un certo nodo e per memorizzare l'insieme P
è consigliabile.
Essendo P un insieme (e non un multiinsieme) è bene
verificare, quando vi si vuole inserire un elemento, che questo non sia
già presente.