Graphen

Lernfeld 11: Funktionalität in Anwendungen realisieren

Was sind Graphen und wie funktionieren sie?

Das Konzept: Vernetzte Daten

In der Informatik ist ein Graph eine vielseitige Datenstruktur, die verwendet wird, um komplexe Beziehungen zwischen Objekten zu modellieren. Während du Arrays und Listen als lineare Strukturen und Bäume als hierarchische Strukturen kennengelernt hast, sind Graphen Netzwerke ohne festen Anfang oder Ende. Sie bestehen aus zwei fundamentalen Bausteinen:

Knoten (Vertices): Diese repräsentieren die Objekte selbst. Das können Städte in einem Navigationssystem, Personen in einem sozialen Netzwerk oder Router im Internet sein.
Kanten (Edges): Diese stellen die Verbindungen zwischen den Knoten dar. Das sind beispielsweise die Straßen zwischen Städten, die Freundschaften zwischen Personen oder die Kabel zwischen Routern.

Graphen sind flexibel, da sie komplexe, nicht-lineare Zusammenhänge abbilden können. Während eine Liste eine strikte Reihenfolge hat (Vorgänger/Nachfolger), kann ein Knoten in einem Graphen mit beliebig vielen anderen Knoten verbunden sein.

Gerichtete und ungerichtete Graphen

Nicht jede Beziehung verläuft in beide Richtungen. Daher unterscheiden wir bei den Kanten:

Ungerichteter Graph: Eine Verbindung gilt immer für beide Seiten. Es gibt keine Pfeilspitze.
- Beispiel: Eine Freundschaft in sozialen Netzwerken. Wenn Anna mit Bert befreundet ist, ist Bert automatisch auch mit Anna befreundet.
- Beispiel: Treppen in einem Gebäude. Wenn du von Stockwerk 1 zu Stockwerk 2 gehen kannst, kannst du auch wieder zurück.
Gerichteter Graph (Digraph): Die Verbindung hat eine klare Richtung (Quelle zu Ziel).
- **Beispiel:* Einbahnstraßen in einem Stadtplan. Du kannst von A nach B fahren, aber nicht direkt von B zurück nach A.
- Beispiel: Ein "Follow" auf Instagram oder Twitter. Wenn du einem Star folgst, folgt dieser dir nicht zwingend zurück.

Gewichtete Graphen: Wenn die Kosten zählen

Oft reicht es nicht zu wissen, dass eine Verbindung besteht, sondern wie beschaffen sie ist.

Ungewichteter Graph: Alle Kanten sind gleichwertig. Es zählt nur die Existenz der Verbindung.
- Beispiel: Ein U-Bahn-Netzplan, der nur anzeigt, welche Stationen direkt verbunden sind, ohne Fahrzeiten zu berücksichtigen.
- Beispiel: Ein soziales Netzwerk, das nur zeigt, wer mit wem befreundet ist, ohne die Intensität der Freundschaft zu bewerten.
Gewichteter Graph: Jeder Kante ist ein Wert (das Gewicht) zugeordnet. Dieser Wert kann Kosten, Distanz oder Zeit repräsentieren.
- Beispiel: Ein Navigationssystem. Die Kante zwischen "München" und "Berlin" trägt das Gewicht "580 km" oder "6 Stunden". Algorithmen nutzen diese Gewichte, um den effizientesten Weg zu berechnen (z. B. kürzeste Strecke).
- Beispiel: Eine Verbindung zwischen Routern im Internet, bei der die Kante das Gewicht "Latenzzeit" oder "Bandbreite" hat, um den besten Pfad für Datenpakete zu bestimmen.

dec-software-engineering-data-structures-and-algorithms-fundamental-data-structures-graphs_page1.svg

Wie werden Graphen im Speicher abgebildet?

Die Adjazenzmatrix: Der Tabellen-Ansatz

Eine Adjazenzmatrix ist eine quadratische Tabelle (ein 2D-Array), bei der sowohl die Zeilen als auch die Spalten die Knoten repräsentieren.

Funktionsweise: Wenn eine Kante von Knoten A zu Knoten B existiert, wird an der Stelle Matrix[A][B] eine 1 (oder das Gewicht der Kante) eingetragen. Gibt es keine Verbindung, steht dort eine 0 (oder unendlich/null).
Vorteil: Der Zugriff ist extrem schnell (O(1)). Um zu prüfen, ob A und B verbunden sind, muss der Computer nur eine einzige Speicherzelle abfragen.
Nachteil: Der Speicherbedarf ist hoch (O(V²), wobei V die Anzahl der Knoten ist). Bei einem Graphen mit 10.000 Knoten werden 100 Millionen Speicherzellen benötigt, auch wenn es nur wenige Kanten gibt.
Einsatz: Ideal für dichte Graphen, bei denen fast jeder Knoten mit jedem anderen verbunden ist.

// Pseudocode: Adjazenzmatrix
Klasse Graph:
    // 2D-Array mit Anzahl Knoten initialisieren
    matrix = new Array[anzahl][anzahl]

    Funktion addEdge(start, ziel):
        matrix[start][ziel] = 1
        // Bei ungerichteten Graphen auch den Rückweg setzen:
        matrix[ziel][start] = 1

    Funktion hasEdge(start, ziel):
        // Direkter Zugriff möglich
        return matrix[start][ziel] == 1

Die Adjazenzliste: Der speicherschonende Ansatz

Hier wird für jeden Knoten eine Liste (z. B. eine Linked List oder ein dynamisches Array) verwaltet, die nur seine direkten Nachbarn enthält.

Funktionsweise: Wir haben ein Array von Listen. Wenn Knoten A (Index 0) mit B (Index 1) verbunden ist, steht in der Liste an Index 0 der Wert 1.
Vorteil: Es wird nur Speicher für tatsächlich existierende Verbindungen verbraucht. Das ist sehr effizient für dünn besetzte Graphen (wenige Kanten im Vergleich zur möglichen Anzahl), wie etwa Straßennetze (eine Kreuzung hat meist nur 3-4 Verbindungen, nicht Tausende).
Nachteil: Um zu prüfen, ob eine Kante zwischen A und B existiert, muss die Liste von A durchsucht werden. Das dauert etwas länger als der direkte Zugriff in der Matrix.

// Pseudocode: Adjazenzliste
Klasse Graph:
    // Array oder Map, das Listen speichert
    adjList = Map()

    Funktion addEdge(start, ziel):
        // Füge 'ziel' zur Liste der Nachbarn von 'start' hinzu
        adjList[start].add(ziel)
        // Bei ungerichteten Graphen auch den Rückweg setzen:
        adjList[ziel].add(start)

    Funktion hasEdge(start, ziel):
        // Muss die Liste durchsuchen
        return adjList[start].contains(ziel)

dec-software-engineering-data-structures-and-algorithms-fundamental-data-structures-graphs_page2.svg

Lernziele

das Konzept von Graphen erklären, indem die grundlegenden Bestandteile (Knoten/Vertices, Kanten/Edges) und die Flexibilität von Graphen zur Modellierung komplexer Beziehungen (z.B. soziale Netzwerke, Routenplanung) erläutert werden.
verschiedene Arten von Graphen differenzieren, indem die Unterschiede zwischen gerichteten und ungerichteten sowie gewichteten und ungewichteten Graphen anhand von Beispielen (z.B. Einbahnstraßen vs. normale Straßen, Entfernungen zwischen Städten) erläutert werden.
die Repräsentation von Graphen im Speicher erklären, indem die Vor- und Nachteile von Adjazenzmatrizen und Adjazenzlisten in Bezug auf Speicherbedarf und Zugriffsgeschwindigkeit für verschiedene Graphentypen (dicht vs. dünn besetzt) gegenübergestellt werden.

← Zurück zu Funktionalität in Anwendungen realisieren

🚀 Bereit für mehr?

Vertiefe dein Wissen!

Du hast die Grundlagen verstanden? Perfekt! In unserer App findest du interaktive Übungen, praktische Projekte und erweiterte Inhalte zu Graphen.

💼 Für Unternehmen

Ab 5€/Monat • Kostenloser Test verfügbar