[JAVA] Implementazione di un grafo

[robs05]

Salve ragazzi qualcuno può darmi qualche indicazione di come imlementare la visita di un grafo orientato in java.

Magari se avete un esempio me lo guardo.

Ringrazio anticipatamente

[71104]

dipende dalle strutture dati che usi per memorizzare il grafo: matrice di adiacenze? oggetti contenenti riferimenti ad altri oggetti? altro?

[robs05]

In effetti a breve dovrei sostenere l'esame di Java, sono preparato bene l'unica preoccupazione è l'implementazione di un grafo, e purtroppo non avendo ancora seguito algoritmi e strutture dati che seguitò ad ottobre mi trovo un pò in difficoltà

ho dato uno sguardo ai grafi, teoricamente il concetto mi è chiaro, ma non so dove iniziare per implemetarlo.

penso che l'implemetazione è libera...

mi voglio preparare comunque perchè se come traccia esce questa sto spiazzato


grazie mille spero che puoi essermi d'aiuto

[71104]

se la scelta delle strutture dati è libera allora dai per scontato che ciascun nodo sia rappresentato da un oggetto avente dei riferimenti agli altri nodi. visitare il grafo è di una semplicità disarmante, devi solo fare attenzione a non andare in loop se esso contiene cicli. io proverei a definire una classe Node e farei una cosa del genere:

public class Node
{
	private Set<Node> neighbors;
	private boolean visited = false;

	public void visit()
	{
		if (visited)
		{
			return;
		}

		visited = true;
		for (Node neighbor : neighbors)
		{
			neighbor.visit();
		}
	}

}

"neighbors" è l'insieme dei nodi adiacenti a this; il flag "visited" invece serve ad evitare che un nodo venga visitato due volte, cosa che manderebbe in loop il programma se il grafo contiene cicli.