Autoren

Hannes Kretschmer

Julian Hilsberg

Grundbegriffe der Graphentheorie

Datenstrukturen für Graphen

Operationen für Graphen

Die Wahl der Darstellung eines Graphen muss immer im Bezug auf die mit den Daten durchzuführenden Operationen erfolgen. Die Operationen sind problemabhängig. Die wichtigsten Operationen für Graphen sind:

• Feststellen, ob ein Paar von Ecken benachbart ist.
• Bestimmung der Nachbarn einer Ecke.
• Bestimmung der Nachfolger und Vorgänger einer Ecke in einem gerichteten Graphen.

Neben der Effizienz der Operationen spielt auch der Speicherplatzverbrauch eine große Rolle, bei der Wahl einer Datenstruktur.