Graph (Datenstruktur)

Kurz: Ein Graph besteht aus Knoten und Kanten, die Knoten verbinden. Er modelliert beliebige Beziehungen: Straßennetze, soziale Netzwerke, Netzwerke von Rechnern, Abhängigkeiten zwischen Paketen.

Genauer: Kanten können gerichtet (Einbahnstraße) oder ungerichtet sein und ein Gewicht tragen (Entfernung, Kosten). Anders als ein Baum darf ein Graph Kreise enthalten und mehrere Wege zwischen Knoten bieten.

Im Detail

Darstellung

• Adjazenzliste: Zu jedem Knoten die Liste seiner Nachbarn – speichereffizient für dünne Graphen.
• Adjazenzmatrix: Tabelle n×n, Eintrag 1 (oder das Gewicht), wenn eine Kante besteht – schneller Kantentest, aber viel Speicher.

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D", "E"],
    "D": ["F"],
    "E": ["F"],
    "F": [],
}
 
from collections import deque
 
def breitensuche(start, ziel):
    besucht = {start}
    schlange = deque([[start]])
    while schlange:
        weg = schlange.popleft()
        knoten = weg[-1]
        if knoten == ziel:
            return weg
        for nachbar in graph[knoten]:
            if nachbar not in besucht:
                besucht.add(nachbar)
                schlange.append(weg + [nachbar])
    return None
 
print(breitensuche("A", "F"))    # ['A', 'B', 'D', 'F']

Wichtige Algorithmen

Aufgabe	Verfahren
Kürzester Weg (ungewichtet)	Breitensuche
Kürzester Weg (gewichtet)	Dijkstra, A*
Alle erreichbaren Knoten	Tiefen- oder Breitensuche
Abhängigkeiten ordnen	Topologische Sortierung
Kürzester Rundweg durch alle Städte	Traveling Salesman (schwer)

Graphen stecken hinter Routenplanern, Empfehlungen („Freunde von Freunden“), Compilern (Abhängigkeitsgraphen) und Graphdatenbanken. Die Suche nutzt einen Stack (Tiefensuche) oder eine Queue (Breitensuche).

Siehe auch: Baum, Queue, Algorithmen, Datenstrukturen