Lernziele

Graphen sind überall

Immer wenn Dinge miteinander verbunden sind, habt ihr einen Graphen — auch ohne es zu merken.

Was ist ein Graph?

Ein Graph besteht aus zwei Dingen: Knoten (die Punkte) und Kanten (die Verbindungen).

Zwei Eigenschaften, die du kennen musst

🤔 Wie speichern wir einen Graphen in C?

Auf Papier ist ein Graph schnell gemalt. Aber ein Computer kennt keine „Punkte und Striche" — er kennt Zahlen, Arrays und Speicheradressen. Wie also?

Variante 1: die Adjazenzmatrix

Eine Tabelle Knoten × Knoten. Steht eine 1 bei Zeile X, Spalte Y → es gibt eine Kante X–Y. Sonst 0.

// A=0, B=1, C=2, D=3, E=4
int graph[5][5] = {
    {0,1,1,0,0},  // A ist mit B,C verbunden
    {1,0,1,1,0},  // B mit A,C,D
    {1,1,0,0,1},  // C mit A,B,E
    {0,1,0,0,1},  // D mit B,E
    {0,0,1,1,0}   // E mit C,D
};
// "Sind B und D verbunden?" → graph[1][3] == 1 ✓

Adjazenzmatrix — stark, aber nicht perfekt

🤔 Wie würdet IHR das besser machen?

Die Matrix verschwendet Platz — fast nur Nullen. Bevor wir eine Lösung zeigen: überlegt kurz selbst.

🤔 Eine natürlichere Idee

Statt einer riesigen Tabelle: was, wenn jeder Knoten einfach eine kleine Liste hätte — „auf diese Nachbarn zeige ich"?

A  →  B, C
B  →  A, C, D
C  →  A, B, E
D  →  B, E
E  →  C, D

Was ist ein Zeiger? — eine Adresse

Der Speicher (RAM) ist wie eine riesige Straße mit nummerierten Häusern. Jede Variable wohnt in einem Haus mit einer Adresse.

Zeiger in C — zwei neue Symbole: & und *

int x = 5;          // normale Variable

int *p = &x;        // p zeigt auf x
//      └─ &x = "die Adresse von x"

printf("%d", *p);  // → 5
//            └ *p = "der Wert, auf den p zeigt"

*p = 9;             // ändert x über den Zeiger!
printf("%d", x);   // → 9

Wofür das gut ist: eine Funktion, die das Original ändert

Bisher haben eure Funktionen mit Kopien gearbeitet — und das ist völlig richtig so. Eine Funktion, die etwas berechnet und zurückgibt, braucht keine Zeiger. Nur wenn eine Funktion die Variablen des Aufrufers selbst verändern soll, reichen Kopien nicht.

void tausche(int a, int b) {
    int t = a; a = b; b = t;
}
// a und b sind nur KOPIEN.
// Draußen ändert sich nichts.

void tausche(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}
tausche(&x, &y);  // Adressen geben
// jetzt sind x und y wirklich
// vertauscht ✓

Der Zeiger ins Nichts: NULL

Achtung — zwei verschiedene Dinge: einen NULL-Zeiger zu haben ist völlig ok. Ihm zu folgen ist der Fehler.

Die große Idee: eine Kante ist ein Zeiger

Der Gedanke in drei Schritten: Kante A—B heißt „von A erreiche ich B".  →  In C heißt „erreichen" = einen Zeiger haben.  →  Also speichert jeder Knoten Zeiger auf seine Nachbarn.

A ──► B ──► C ──► ∅
B ──► A ──► C ──► D ──► ∅
C ──► A ──► B ──► E ──► ∅
D ──► B ──► E ──► ∅
E ──► C ──► D ──► ∅

Matrix vs. Liste — wann was?

Die Kernfrage: Wie durchsuche ich einen Graphen?

Zwei der häufigsten Fragen der Informatik:

BFS — wie eine Welle im Wasser

Wirf einen Stein ins Wasser: die Welle erreicht erst alle nahen Punkte, dann die nächst-ferneren. BFS erkundet den Graphen genau so — Ebene für Ebene.

Das Werkzeug von BFS: die Warteschlange (Queue)

Beim Erkunden entdeckt ihr laufend neue Knoten — besuchen könnt ihr aber immer nur einen nach dem anderen. Die übrigen müsst ihr euch merken. Genau dafür die Queue: eine To-do-Liste der Knoten „entdeckt, aber noch nicht besucht".

BFS Schritt für Schritt — Start bei A

Die Welle wächst — ● Start, ● Abstand 1, ● Abstand 2:

Queue ≠ besucht — zwei getrennte Listen

Häufige Frage: „Wenn ich einen Knoten aus der Queue nehme — ist er dann nicht weg?" Nein: es gibt zwei Listen mit zwei Aufgaben. Schaut, was bei einem Schritt passiert (A wird bearbeitet):

Der Clou: BFS findet den kürzesten Weg

Nebenbei liefert BFS etwas Wertvolles gratis — den kürzesten Weg (in Schritten). Aber warum eigentlich?

🚗 Nächste Woche: wenn Wege unterschiedlich teuer sind

BFS sagt „nimm den Weg mit den wenigsten Kanten". Aber das ist nicht immer der schnellste.

🤔 Mini-Quiz

🤔 Mini-Quiz — Runde 2

Zusammenfassung — in einer Slide

📚 Quellen & zum Ausprobieren