Lab 6: Graphen, Zeiger & BFS

← Startseite

🧠 Worum geht es?

In Vorlesung 10 ging es um Graphen & Zeiger — was ein Graph ist (Knoten + Kanten), wie man ihn als Adjazenzmatrix speichert, was ein Zeiger ist (eine Adresse), und wie BFS einen Graphen Schicht für Schicht durchsucht und dabei den kürzesten Weg findet.

Heute baut ihr das alles selbst: von Zeigern über die Adjazenzmatrix bis zu BFS mit eigener Queue. Dazwischen schließen wir die zwei Werkzeuge ein, die in der Vorlesung nur als Bild auftauchten (A ──► B ──► C ──► ∅), aber noch nicht im Code: struct (Daten bündeln) und malloc (Speicher zur Laufzeit anfordern). Damit verwandelt ihr die gemalte „Nachbarliste" in echten C-Code.

🌐 Programmiersprache

Alle Aufgaben sind reines C — ohne externe Bibliotheken, sie laufen überall mit gcc lab.c. Wer in einer anderen Sprache arbeitet: Die Algorithmen (Adjazenzmatrix, Nachbarliste, BFS) sind 1:1 übertragbar. Nur zwei C-Eigenheiten haben in höheren Sprachen kein direktes Gegenstück: struct entspricht einer Klasse/einem Objekt (Python class, Java-Objekt), und malloc/free entfällt — dort verwaltet die Sprache den Speicher automatisch (Listen, new, Garbage Collection).

Musterlösungen liegen nur in C vor. Passwörter sind ganz unten frei zugänglich.

🎯 Lernziele

📍 Zeiger anwenden

Adresse vs. Wert, etwas über einen Zeiger ändern, tausche mit *

🗺️ Graphen speichern

Adjazenzmatrix lesen, Nachbarn finden, Verbindungen prüfen

📦 struct & malloc

Daten bündeln, Speicher zur Laufzeit anfordern und freigeben

🌊 BFS bauen

Queue + besucht-Liste, kürzeste Distanz Schicht für Schicht

🗺️ Unser Beispielgraph (für das ganze Lab)

Wir benutzen durchgehend denselben kleinen, ungerichteten Graphen aus der Vorlesung — 5 Knoten A B C D E (intern 0 1 2 3 4):

A — B, C B — A, C, D C — A, B, E D — B, E E — C, D

Behalte dieses Bild im Kopf — jede Aufgabe arbeitet mit genau diesem Graphen.

1 Zeiger aufwärmen ⏱️ 15 Min VL 10: Zeiger

Ziel: den Unterschied zwischen Wert und Adresse mit eigenen Händen spüren — und sehen, wie eine Funktion das Original ändert, wenn man ihr die Adresse gibt.

Aufgabe:

Lege int x = 5; an und einen Zeiger int *p = &x; (p zeigt auf x).
Gib x und *p aus. Ändere dann x über den Zeiger mit *p = 42; und gib x erneut aus.
Schreibe tausche(int *a, int *b), das zwei Variablen vertauscht — über ihre Adressen. Teste mit tausche(&x, &y);.

🤔 Denkfrage: Würde tausche mit normalen Parametern (int a, int b) funktionieren? Nein — die Funktion bekäme nur Kopien, draußen ändert sich nichts. Erst die Adresse (&x) erlaubt es, das Original zu verändern. Genau dieses Prinzip steckt hinter Zeigern auf Graphen, structs und allem, was gleich kommt.

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>

void tausche(int *a, int *b) {
    int t = *a;      // Wert, auf den a zeigt
    *a = *b;
    *b = t;
}

int main(void) {
    int x = 5, y = 9;
    int *p = &x;                  // p zeigt auf x

    printf("x = %d, *p = %d\n", x, *p);      // 5, 5
    *p = 42;                                  // x UEBER den Zeiger aendern
    printf("nach *p = 42: x = %d\n", x);      // 42

    printf("vorher:  x = %d, y = %d\n", x, y);
    tausche(&x, &y);              // Adressen uebergeben
    printf("nachher: x = %d, y = %d\n", x, y);
    return 0;
}

Erwartete Ausgabe:

x = 5, *p = 5
nach *p = 42: x = 42
vorher:  x = 42, y = 9
nachher: x = 9, y = 42

2 Der Graph als Adjazenzmatrix ⏱️ 20 Min VL 10: Graphen

Ziel: den Beispielgraphen als Adjazenzmatrix speichern und zwei Grundfragen beantworten: „Sind zwei Knoten verbunden?" und „Wer sind die Nachbarn eines Knotens?"

Aufgabe:

Lege int graph[5][5] an. graph[i][j] == 1 bedeutet: Kante zwischen i und j.
Prüfe, ob B(1) und D(3) verbunden sind — also graph[1][3].
Gib alle Nachbarn von C(2) aus: laufe Zeile 2 durch und drucke jeden Knoten j mit graph[2][j] == 1.

💡 Hinweis: Weil der Graph ungerichtet ist, ist die Matrix symmetrisch: graph[i][j] ist immer gleich graph[j][i]. „Nachbarn finden" heißt einfach: eine Zeile durchlaufen.

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>

int main(void) {
    // A=0, B=1, C=2, D=3, E=4
    int graph[5][5] = {
        {0,1,1,0,0},   // A - B,C
        {1,0,1,1,0},   // B - A,C,D
        {1,1,0,0,1},   // C - A,B,E
        {0,1,0,0,1},   // D - B,E
        {0,0,1,1,0}    // E - C,D
    };
    char namen[5] = {'A','B','C','D','E'};

    // Sind B(1) und D(3) verbunden?
    printf("B-D verbunden? %d\n", graph[1][3]);   // 1 = ja

    // Nachbarn von C(2)
    printf("Nachbarn von C: ");
    for (int j = 0; j < 5; j++) {
        if (graph[2][j] == 1) printf("%c ", namen[j]);
    }
    printf("\n");
    return 0;
}

Erwartete Ausgabe:

B-D verbunden? 1
Nachbarn von C: A B E

3 struct — Daten bündeln ⏱️ 20 Min 🆕 Theorie-Vorgriff

📐 Kurz-Theorie: Was ist ein `struct`?

Bisher lag dein Graph in mehreren losen Variablen herum: die Matrix hier, die Namen dort, die Knotenzahl irgendwo. Ein struct bündelt zusammengehörige Daten unter einem Namen — wie ein Steckbrief mit mehreren Feldern.

struct Graph { int n; // Anzahl Knoten int matrix[5][5]; // die Adjazenzmatrix char namen[5]; // Knotennamen };

Auf die Felder greifst du mit dem Punkt-Operator zu: g.n, g.matrix[1][3], g.namen[2]. So reist der ganze Graph als ein Ding durch dein Programm.

Aufgabe:

Definiere ein struct Graph mit den Feldern n, matrix[5][5] und namen[5].
Lege eine Variable struct Graph g an und fülle sie mit unserem Beispielgraphen.
Gib g.n aus und die Nachbarn von B(1) — diesmal über g.matrix und g.namen.

🤔 Denkfrage: Warum ist das praktisch? Stell dir eine Funktion void drucke(struct Graph g) vor — du übergibst einen Parameter statt drei. In Python/Java wäre struct eine Klasse; in C ist es dasselbe in Grün, nur ohne Methoden.

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>

// Ein struct buendelt zusammengehoerige Daten unter EINEM Namen
struct Graph {
    int  n;              // Anzahl Knoten
    int  matrix[5][5];   // Adjazenzmatrix
    char namen[5];       // Knotennamen
};

int main(void) {
    struct Graph g = {
        5,
        {
            {0,1,1,0,0},
            {1,0,1,1,0},
            {1,1,0,0,1},
            {0,1,0,0,1},
            {0,0,1,1,0}
        },
        {'A','B','C','D','E'}
    };

    // Zugriff mit dem Punkt-Operator
    printf("Knoten: %d\n", g.n);
    printf("Nachbarn von %c: ", g.namen[1]);    // B
    for (int j = 0; j < g.n; j++) {
        if (g.matrix[1][j] == 1) printf("%c ", g.namen[j]);
    }
    printf("\n");
    return 0;
}

Erwartete Ausgabe:

Knoten: 5
Nachbarn von B: A C D

4 malloc — Speicher zur Laufzeit ⏱️ 20 Min 🆕 Theorie-Vorgriff

📐 Kurz-Theorie: Was macht `malloc`?

Bisher kanntest du nur Arrays mit fester Größe: int besucht[5]; — die Zahl muss schon beim Schreiben des Programms feststehen. Aber was, wenn die Knotenzahl erst zur Laufzeit bekannt ist (z. B. aus einer Datei)?

malloc („memory allocate") fordert genau so viel Speicher an, wie du brauchst, und gibt dir einen Zeiger auf den Anfang zurück:

int *besucht = malloc(n * sizeof(int)); // Platz fuer n int ... free(besucht); // wieder freigeben!

Ein besucht[i] funktioniert danach genau wie bei einem normalen Array. Wichtig: Was du mit malloc holst, musst du mit free wieder zurückgeben — sonst entsteht ein Speicherleck.

Aufgabe:

Setze eine Knotenzahl n = 5.
Fordere mit malloc(n * sizeof(int)) ein besucht-Array an und setze alle Einträge auf 0.
Markiere Knoten C(2) als besucht (besucht[2] = 1), gib das Array aus und gib den Speicher mit free wieder frei.

⚠️ Zwei Regeln: <stdlib.h> einbinden (dort wohnen malloc/free), und jedes malloc braucht am Ende sein free. Dieses besucht-Array ist exakt das, was BFS in Aufgabe 6 braucht.

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>
#include <stdlib.h>     // malloc, free

int main(void) {
    int n = 5;

    // Speicher zur LAUFZEIT anfordern: Platz fuer n int
    int *besucht = malloc(n * sizeof(int));

    for (int i = 0; i < n; i++) {
        besucht[i] = 0;        // 0 = noch nicht besucht
    }

    besucht[2] = 1;            // Knoten C als besucht markieren

    for (int i = 0; i < n; i++) {
        printf("besucht[%d] = %d\n", i, besucht[i]);
    }

    free(besucht);             // Speicher IMMER wieder freigeben
    return 0;
}

Erwartete Ausgabe:

besucht[0] = 0
besucht[1] = 0
besucht[2] = 1
besucht[3] = 0
besucht[4] = 0

5 Die Adjazenzliste — struct + malloc + Zeiger ⏱️ 30 Min VL 10: Graphen

Ziel: das Bild aus der Vorlesung — C ──► A ──► B ──► E ──► ∅ — in echten Code verwandeln. Eine Adjazenzliste ist für jeden Knoten eine kleine verkettete Liste seiner Nachbarn. Hier kommen alle drei neuen Werkzeuge zusammen: struct (ein Listenknoten), malloc (jeden Knoten anlegen) und Zeiger (next zeigt auf den nächsten).

📐 Die Idee: ein Listenknoten zeigt auf den nächsten

struct Node { int ziel; // Index eines Nachbarn struct Node *next; // Zeiger auf den naechsten Nachbarn (oder NULL) };

Ein struct Node *adj[5] ist dann ein Array von Listenanfängen: adj[i] zeigt auf den ersten Nachbarn von Knoten i. Das Listenende ist NULL (das ∅ aus der Vorlesung).

📐 Neu: eine Funktion, die einen Zeiger zurückgibt

In VL 10 hast du Funktionen gesehen, die einen Zeiger bekommen (z. B. tausche(int *a, int *b) aus Aufgabe 1). Jetzt machen wir den kleinen Schritt weiter: eine Funktion, die einen Zeiger zurückgibt. Der Rückgabetyp ist dann kein int, sondern struct Node * — „ein Zeiger auf einen Node":

struct Node* anhaengen(struct Node *liste, int ziel) { struct Node *neu = malloc(sizeof(struct Node)); neu->ziel = ziel; neu->next = liste; // neuer Knoten zeigt auf den alten Anfang return neu; // gib den NEUEN Anfang zurueck }

Warum überhaupt etwas zurückgeben? Weil sich der Anfang der Liste ändert: Der frisch per malloc erzeugte Knoten wird zum neuen ersten Element. Die Funktion reicht dir diesen neuen Anfang zurück, und du speicherst ihn wieder in adj[i]:

adj[2] = anhaengen(adj[2], 0); // adj[2] zeigt jetzt auf den neuen Knoten

Lies das wie x = x + 1: rechts der alte Stand rein, links das Ergebnis wieder zurück. Mehr ist es nicht — derselbe Zeiger-Typ wie immer, nur diesmal als Rückgabe.

Aufgabe:

Definiere struct Node mit ziel und next.
Schreibe anhaengen(liste, ziel): per malloc einen neuen Knoten anlegen, vorne einhängen, neuen Listenanfang zurückgeben.
Baue für C(2) die Nachbarn A(0), B(1), E(4) auf und laufe die Liste mit p = p->next durch.

💡 Hinweis — der Pfeil ->: Wenn p ein Zeiger auf ein struct ist, schreibt man p->ziel statt (*p).ziel. Der Pfeil heißt: „folge dem Zeiger und nimm dann das Feld". Genau dafür stehen die Pfeile aus der Vorlesung.

🤔 Matrix vs. Liste: Die Matrix aus Aufgabe 2 braucht immer n × n Speicher — auch bei wenigen Kanten. Die Liste speichert nur, was wirklich da ist. Bei großen, „dünnen" Graphen (wenige Kanten pro Knoten) ist die Liste deutlich sparsamer — der Grund, warum es beide Darstellungen gibt.

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>
#include <stdlib.h>

// Ein Knoten der verketteten Liste: ein Nachbar + Zeiger auf den naechsten
struct Node {
    int ziel;             // Index des Nachbarknotens
    struct Node *next;    // naechster Nachbar (oder NULL = Ende)
};

// Haengt einen neuen Nachbarn VORNE an die Liste an
struct Node* anhaengen(struct Node *liste, int ziel) {
    struct Node *neu = malloc(sizeof(struct Node));
    neu->ziel = ziel;
    neu->next = liste;     // neuer Knoten zeigt auf den bisherigen Anfang
    return neu;            // neuer Anfang
}

int main(void) {
    char namen[5] = {'A','B','C','D','E'};

    // adj[i] = Anfang der Nachbarliste von Knoten i
    struct Node *adj[5] = {NULL, NULL, NULL, NULL, NULL};

    // C(2) hat Nachbarn A(0), B(1), E(4)
    adj[2] = anhaengen(adj[2], 0);
    adj[2] = anhaengen(adj[2], 1);
    adj[2] = anhaengen(adj[2], 4);

    // Liste von C durchlaufen
    printf("Nachbarn von C: ");
    for (struct Node *p = adj[2]; p != NULL; p = p->next) {
        printf("%c ", namen[p->ziel]);
    }
    printf("\n");
    return 0;
}

Erwartete Ausgabe:

Nachbarn von C: E B A

Hinweis zur Reihenfolge: Wir hängen jeden neuen Nachbarn vorne an, deshalb erscheinen sie umgekehrt (E B A statt A B E). Für einen Graphen ist das egal — die Menge der Nachbarn zählt, nicht ihre Reihenfolge.

6 BFS — Breitensuche mit eigener Queue ⏱️ 30 Min VL 10: BFS

Ziel: den zentralen Algorithmus der Vorlesung selbst bauen — BFS durchsucht den Graphen wie eine Welle im Wasser: erst alle direkten Nachbarn, dann deren Nachbarn, Schicht für Schicht. Das Werkzeug dafür ist eine Queue (zuerst rein, zuerst raus) plus eine besucht-Liste.

📐 BFS in Worten

1. Start in die Queue, als besucht markieren 2. solange Queue nicht leer: nimm vorderstes Element (aktuell) fuer jeden Nachbarn von aktuell: wenn noch nicht besucht: markiere besucht UND haenge in die Queue

Queue ≠ besucht — zwei getrennte Dinge: Die Queue ist die Warteschlange „noch abzuarbeiten", besucht verhindert, dass ein Knoten doppelt eingereiht wird.

Aufgabe:

Benutze die Adjazenzmatrix aus Aufgabe 2. Realisiere die Queue als int queue[5] mit zwei Indizes kopf (lesen) und ende (schreiben).
Starte BFS bei A(0) und gib die Knoten in Besuchsreihenfolge aus.

💡 Hinweis: Eine Queue im Array ganz ohne Zeiger: queue[ende++] = x; hängt hinten an, int x = queue[kopf++]; nimmt vorne weg. Solange kopf < ende, ist noch etwas drin.

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>

#define N 5

int main(void) {
    int graph[N][N] = {
        {0,1,1,0,0},
        {1,0,1,1,0},
        {1,1,0,0,1},
        {0,1,0,0,1},
        {0,0,1,1,0}
    };
    char namen[N] = {'A','B','C','D','E'};

    int besucht[N] = {0};
    int queue[N];
    int kopf = 0, ende = 0;      // kopf = lesen, ende = schreiben

    int start = 0;               // A
    besucht[start] = 1;
    queue[ende++] = start;

    printf("BFS ab A: ");
    while (kopf < ende) {
        int aktuell = queue[kopf++];         // vorne aus der Queue
        printf("%c ", namen[aktuell]);

        for (int j = 0; j < N; j++) {        // alle Nachbarn
            if (graph[aktuell][j] == 1 && besucht[j] == 0) {
                besucht[j] = 1;              // erst markieren ...
                queue[ende++] = j;           // ... dann einreihen
            }
        }
    }
    printf("\n");
    return 0;
}

Erwartete Ausgabe:

BFS ab A: A B C D E

Warum diese Reihenfolge? Schicht 0 = A; Schicht 1 = die direkten Nachbarn B, C; Schicht 2 = deren neue Nachbarn D, E. Die Welle breitet sich aus.

7 BFS findet den kürzesten Weg ⏱️ 25 Min · BONUS VL 10: BFS

Ziel: den „Clou" aus der Vorlesung beweisen — BFS liefert nicht nur eine Reihenfolge, sondern die kürzeste Distanz (Anzahl Kanten) vom Start zu jedem Knoten. Der Trick: ein dist-Array statt einer reinen Ja/Nein-Markierung.

Aufgabe:

Ersetze besucht durch int dist[N], initialisiert mit -1 (= „noch nicht erreicht", dient gleichzeitig als besucht-Markierung).
Setze dist[start] = 0. Beim Einreihen eines Nachbarn: dist[j] = dist[aktuell] + 1;.
Gib am Ende für jeden Knoten die Distanz von A aus.

🤔 Denkfrage: Warum ist die erste Distanz, die ein Knoten bekommt, automatisch die kürzeste? Weil BFS Schicht für Schicht vorgeht — ein Knoten wird zwangsläufig zuerst über den kürzesten Weg erreicht. Das gilt aber nur, solange alle Kanten gleich „teuer" sind. Sobald Wege unterschiedlich viel kosten (Entfernung, Zeit), braucht man Dijkstra — der nächste Schritt nach diesem Lab.

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>

#define N 5

int main(void) {
    int graph[N][N] = {
        {0,1,1,0,0},
        {1,0,1,1,0},
        {1,1,0,0,1},
        {0,1,0,0,1},
        {0,0,1,1,0}
    };
    char namen[N] = {'A','B','C','D','E'};

    int dist[N];
    for (int i = 0; i < N; i++) dist[i] = -1;    // -1 = noch nicht erreicht

    int queue[N];
    int kopf = 0, ende = 0;

    int start = 0;               // A
    dist[start] = 0;
    queue[ende++] = start;

    while (kopf < ende) {
        int aktuell = queue[kopf++];
        for (int j = 0; j < N; j++) {
            if (graph[aktuell][j] == 1 && dist[j] == -1) {
                dist[j] = dist[aktuell] + 1;      // ein Schritt weiter
                queue[ende++] = j;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        printf("A -> %c: %d Schritte\n", namen[i], dist[i]);
    }
    return 0;
}

Erwartete Ausgabe:

A -> A: 0 Schritte
A -> B: 1 Schritte
A -> C: 1 Schritte
A -> D: 2 Schritte
A -> E: 2 Schritte

D und E sind 2 Schritte weg (z. B. A→B→D bzw. A→C→E) — genau die kürzeste Kantenzahl.

🔑 Passwörter für die Musterlösungen

Die Passwörter stehen unten — frei zugänglich. Bitte fair spielen: erst selbst implementieren, dann mit der Musterlösung vergleichen. Eine Lösung, die ihr nur abgeschrieben habt, hilft euch in der Klausur nicht.

Aufgabe	Thema	Passwort
Aufgabe 1	Zeiger aufwärmen	`zeiger`
Aufgabe 2	Adjazenzmatrix	`matrix`
Aufgabe 3	struct — Daten bündeln	`struct`
Aufgabe 4	malloc — Speicher zur Laufzeit	`malloc`
Aufgabe 5	Adjazenzliste (struct + malloc)	`liste`
Aufgabe 6	BFS mit Queue	`bfs`
Aufgabe 7	BFS kürzester Weg (Bonus)	`distanz`

Hinweis für Python/Java/Rust-Lösungen: die Algorithmen sind 1:1 übertragbar — struct wird zur Klasse/zum Objekt, malloc/free entfällt. Eigene Musterlösungen für jede Sprache gibt es nicht.

🌊 Graphen, Zeiger & BFS — beherrscht

Ihr habt heute den Bogen gespannt — von Zeigern über die Adjazenzmatrix, dann mit struct und malloc die gemalte Nachbarliste in echten Code verwandelt, und zum Schluss BFS mit eigener Queue gebaut, das sogar den kürzesten Weg findet. Ihr wisst jetzt nicht nur, was ein Graph ist, sondern wie man ihn speichert und durchsucht.

Als Nächstes: wenn Wege unterschiedlich teuer sind — der Sprung von BFS zu Dijkstra.

← Startseite

🧠 Worum geht es?

🌐 Programmiersprache

🎯 Lernziele

📍 Zeiger anwenden

🗺️ Graphen speichern

📦 struct & malloc

🌊 BFS bauen

🗺️ Unser Beispielgraph (für das ganze Lab)

1 Zeiger aufwärmen ⏱️ 15 Min VL 10: Zeiger

Aufgabe:

2 Der Graph als Adjazenzmatrix ⏱️ 20 Min VL 10: Graphen

Aufgabe:

3 struct — Daten bündeln ⏱️ 20 Min 🆕 Theorie-Vorgriff

📐 Kurz-Theorie: Was ist ein struct?

Aufgabe:

4 malloc — Speicher zur Laufzeit ⏱️ 20 Min 🆕 Theorie-Vorgriff

📐 Kurz-Theorie: Was macht malloc?

Aufgabe:

5 Die Adjazenzliste — struct + malloc + Zeiger ⏱️ 30 Min VL 10: Graphen

📐 Die Idee: ein Listenknoten zeigt auf den nächsten

📐 Neu: eine Funktion, die einen Zeiger zurückgibt

Aufgabe:

6 BFS — Breitensuche mit eigener Queue ⏱️ 30 Min VL 10: BFS

📐 BFS in Worten

Aufgabe:

7 BFS findet den kürzesten Weg ⏱️ 25 Min · BONUS VL 10: BFS

Aufgabe:

🔑 Passwörter für die Musterlösungen

🌊 Graphen, Zeiger & BFS — beherrscht

📐 Kurz-Theorie: Was ist ein `struct`?

📐 Kurz-Theorie: Was macht `malloc`?