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.