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 Methode folgt einem uninformierten Suchverfahren (uninformiert bedeutet hier, dass dem Verfahren über die Einträge der Adjazenzmatrix hinaus keine weiteren Informationen zur Verfügung stehen) mit dem Namen Tiefensuche (engl. depth-first search, DFS). "Bei der Tiefensuche wird zunächst jeder Pfad vollständig in die Tiefe beschritten, bevor abzweigende Pfade beschritten werden." (siehe den entsprechenden Artikel in Wikipedia, der auch eine schöne Animation dazu zeigt).

Ein zweites uninformiertes Suchverfahren wäre die Breitensuche (engl. breadth-first search, BFS). Bei dieser werden "zunächst alle Knoten beschritten, die vom Ausgangsknoten direkt erreichbar sind. Erst danach werden Folgeknoten beschritten." (siehe den entsprechenden Artikel in Wikipedia, und die sehr anschauliche Animation dort.)

Keines der beiden Suchverfahren ist für das allgemeine Problem der Suche in Graphen „besser“ geeignet als das andere.