Informatik 11

Der Algorithmus zur Breitensuche kann auf einfache Art so abgewandelt werden, dass sich damit ermitteln lässt, ob ein Graph zusammenhängend ist oder nicht. Scheibe - ausgehend vom oben gegebenen Programm - eine Methode istZusammenhängend, die genau dann true zurückgibt, wenn der in der Adjazenzmatrix gespeicherte Graph zusammenhängend ist.

Wir beginnen bei einem beliebigen Startknoten (wir nehmen einfach den ersten), durchlaufen ausgehend von diesem den Graphen mit der Breitensuche und überprüfen am Ende durch Auswertung des Arrays besucht, ob es einen Knoten gibt, der noch nicht besucht wurde. Genau in diesem Fall ist der Graph nicht zusammenhängend.

Warnung:

Soll der Code wirklich auf den Ausgangszustand zurückgesetzt werden?

Alle von Dir gemachten Änderungen werden damit verworfen.

Abbrechen

OK

NaN million steps/s

1

Graph g = new Graph(8);

Code Reset

Ausgabe

Variablen

Programm beendet

Bitte geben Sie eine Zahl ein!

OK

VARIABLEN

BEOBACHTEN

CALL STACK

THREADS

Tipp:

Die Variablen sind nur dann sichtbar, wenn das Programm

• im Einzelschrittmodus ausgeführt wird(Klick auf ),
• an einem Breakpoint hält (Setzen eines Breakpoints mit Mausklick links neben den Zeilennummern und anschließendes Starten des Programms mit ) oder
• in sehr niedriger Geschwindigkeit ausgeführt wird (weniger als 10 Schritte/s).