Zusammenhangskomponenten eines Graphen ausgeben

[starbug]

Hallo allerseits, ich habe mal wieder Probleme mit einer Aufgabe. Wie gesagt sollen die Zusammenhangskomponenten eines Graphen ausgegeben werden. Ich zeige euch mal hier die Klassen.

import java.util.*;

// Zusammen mit den Klassen KnotenTyp und Verbindung wird eine Datenstruktur
// für Graphen in Listendarstellung realisiert

// Die Klasse Graph soll um Methoden zur Ausgabe aller Zusammenhangskomponenten
// des Graphen erweitert werden (siehe /* ToDo */)
class Graph
{
	// Attribute
	private  static int knotenzahl;
	private static boolean[] besucht;
	private KnotenTyp [] knoten;


	// Konstruktor
	Graph( int n)
	{
		knotenzahl = n;
		knoten = new KnotenTyp[knotenzahl];
	}

	// setze Knoten mit Index k auf knoten
	public void setKnoten(int k, KnotenTyp knoten)
	{
		try
		{
			this.knoten[k] = knoten;
		}
		catch(ArrayIndexOutOfBoundsException e)
		{
        	System.err.println("Caught in setKnoten() of class Graph "
                     + "ArrayIndexOutOfBoundsException: "
                     +   e.getMessage());
		}

	}

	// Ermittelt alle Zusammenhangskomponenten des Graphen
	// Es dürfen weitere Hilfsmethoden deklariert und von connectedComponets()
	// aus aufgerufen werden
	// Beispielausgabe:
	// Zusammenhangskomponente 1 besteht aus folgenden Knoten:
	// Name1
	// Name9
	// usw.
	// Zusammenhangskomponente 2 besteht aus folgenden Knoten:
	// Name7
	// Name12
	// usw.
	void connectedComponents()
	{
			// To Do
	}
	
	


	public static void main(String[] args)
	{

		// Graph: Tabelle der Fussball Bundesliga  (Auszug)
		Graph Fussball = new Graph(3);

		Fussball.setKnoten(0, new KnotenTyp ("BV 09 Borussia Dortmund (Deutscher Meister 2011)", null));

		Fussball.setKnoten(1, new KnotenTyp ("FC Schalke 04",
															new Verbindung (13, 0, null)));

		Fussball.setKnoten(2, new KnotenTyp ("VfL Borussia Mönchengladbach",
															new Verbindung (15, 0, null)));


		System.out.println("Zusammenhangskomponenten von Graph Fussball:");
		Fussball.connectedComponents();
}

// Knoten für die Realisierung einer Datenstruktur
// für Graphen in Listendarstellung
// Der Knoten enthält einen Namen und einen Verweis
// auf seine Nachbarn
// Die Nachbarn sind als verkettete Liste gespeichert
// (siehe Klasse Verbindung)
class KnotenTyp
{
	private String derName;
	Verbindung nachbarn;

	KnotenTyp (String s, Verbindung v)
	{
	    derName = s;
	    nachbarn = v;
	}

	public String getName()
	{
		return derName;
			
	}

}

// Verbindungselement für die Realisierung einer Datenstruktur
// für Graphen in Listendarstellung
// Die Verbindung (engl. link) enthält eine Kantenbewertung, ein Ziel
// (Index eines Knotens) und eine Referenz auf die folgende
// Verbindung, im Sinne einer verketteten linearen Liste

class Verbindung
{
	private int bewertung;
	private int ziel;
	Verbindung weitere;

	Verbindung (int b, int z, Verbindung v)
	{
		bewertung = b;
		ziel = z;
		weitere = v;
	}

	public int getBewertung()
	{
		return bewertung;
	}

	public int getZiel()
	{
		return ziel;
	}
}

Meine Idee wäre es ja nun mit einer Tiefensuche den Graphen zu durchlaufen, aber da bin ich mir nicht sicher wie man so etwas macht? Vielleicht mit einem Iterator? Mein zweites Problem ist dann wie ich die einzelnen Knoten markieren kann, sodass ich weiss ob ich diese schon besucht habe. Für Anregungen imm dankbar

 

[Technoblade]

Wenn du dir deinen Quelltext mal durchgelesen hast, dann sollte dir aufgefallen sein, dass es da folgende Zeile gibt:

private static boolean[] besucht;

Damit dürfte sich deine Frage danach wie du besuchte Knoten makierst doch erledigt haben, oder?

 

[starbug]

Ja aber ich bekomme das leider nicht hin, also hab auch schon was im netz gefunden

http://www.inf.fh-flensburg.de/lang/algorithmen/graph/connected-components.htm

aber das sind die Methoden ein wenig anders. Ich versteh ja was ich machen muss, aber ichweiss nicht wie ich das umstellen soll.