Graphen bestehen aus Knoten und Kanten. Kanten verbinden jeweils zwei Knoten. Kanten können gerichtet sein (d.h. sie können nur in einer Richtung durchlaufen werden, ähnlich wie eine Einbahnstraße) oder ungerichtet und sie können Gewichte besitzen (z.B. Länge einer Strecke). Die Gewichte werden an den Kanten notiert. Graphen, deren Kanten keine Gewichte besitzen, heißen ungewichtet (auch: unbewertet).

Folgen von Kanten, die zwei Knoten verbinden heißen Pfad. Ein Pfad, dessen Anfangs- und Endknoten übereinstimmt heißt geschlossener Pfad. Ein Knoten A heißt von einem anderen Knoten B aus erreichbar, wenn es von B nach A einen Pfad gibt. Ein geschlossener Pfad, der keine Kante zweimal enthält, heißt Zyklus. Ein Graph, der mindestens einen Zyklus besitzt, heißt zyklisch.

Ein ungerichteter Graph heißt zusammenhängend, wenn von jedem Knoten zu jedem anderen ein Pfad existiert.

Ein gerichteter Graph heißt

• stark zusammenhängend, wenn von jedem Knoten zu jedem anderen ein Pfad existiert
  (damit ist natürlich insbesondere gemeint, dass die Kanten in der vorgegebenen Richtung durchlaufen werden),
• schwach zusammenhängend, wenn er als ungerichteter Graph zusammenhängend wäre und
• ansonsten unzusammenhängend (auch bei ungerichteten Graphen).

Die oben verwendete graphische Darstellung ist zwar anschaulich, für algorithmische Verarbeitung aber häufig eher ungünstig. Eine andere Darstellung von Graphen ist ihre Adjazenzmatrix (man nennt zwei Knoten, die durch eine Kante verbunden sind, auch adjazent). Dabei wird eine Art Tabelle aufgestellt, deren Spalten- und Zeilenanzahl der Anzahl der Knoten entspricht (die im Folgenden verwendeten Zeilen- und Spaltenbeschriftungen sind nicht Teil der Adjazenzmatrix und dienen nur der Veranschaulichung). Die Adjazenzmatrix enthält dann als Eintrag

• 0, wenn es keine Kante zwischen dem links stehenden und dem oben stehenden Knoten gibt
• 1, wenn es eine Kante zwischen den Knoten gibt und der Graph ungewichtet ist
• ansonsten das Kantengewicht

Zweidimensionales int-Array?

Du erinnerst Dich vielleicht noch an eindimensionale Arrays, z.B.

int[] zahlen = new int[7];   //Das Array zahlen enthält 7 Elemente: zahlen[0] bis zahlen[6].
zahlen[0] = 12;              // speichert im ersten Element die Zahl 12
zahlen[5] = 4;               // speichert im 6. Element die Zahl 4;
println(zahlen[5]);   // Gibt das 6. Element aus

Falls Du Dein Wissen über Arrays auffrischen möchtest, schau' Dir die Wiki-Seite aus Jgst. 10 dazu an!

Hier zur Wiederholung eine kleine Fingerübung zu eindimensionalen Arrays (Umkehrung eines Arrays).
Ein zweidimensionales Array speichert "ein Schachbrett voller Zahlen". Die Speicherung von bspw. $4 \times 3$ Zahlen geht so:

int[][] zahlen = new int[4][3];    // Der erste Index geht von 0 bis 3, der zweite von 0 bis 2
zahlen[2][1] = 10;
zahlen[0][2] = 14;

Man kann sich vorstellen, dass das Array zahlen aufgebaut ist wie ein Schachbrett. Der erste Index bezeichnet die Zeile des Feldes, der zweite die Spalte. Nach Ablauf dieses Programms sieht die Belegung des Arrays so aus:

Im Array gespeichert sind natürlich nur die 12 Werte der blauen Zellen. Die fettgedruckten Zeilen- bzw. Spaltenköpfe dienen nur zur Veranschaulichung.

Die Behandlung der Tiefensuche ist im Lehrplan leider nicht vorgesehen. Weil dieser Algorithmus sich sehr gut eignet, um einen Einblick in die Programmierung mithilfe von rekursiven Methodenaufrufen zu bekommen, finden interessierte Schüler/innen hier eine Einführung zum Selbststudium. Falls Sie Fragen dazu haben, stehe ich gerne zur Verfügung!