bei Ariadne zurück

Datenstrukturen allgemein


Adjazenzmatrix

Datentyp ARRAY

Die "einfachste" Form der Datendarstellung ist eine Matrix, bei der man den Feldinhalt an einer speziellen Position durch einen direkten Zugriff über die Indizes ( Koordinaten ) herauslesen kann. Die Inhalte der Felder in der Matrix an der Position (i , j) kennzeichnen, ob eine Kante von der Ecke i zur Ecke j führt.

Bei einem ungerichteten Graphen sind alle Einträge an den Positionen (i , j) mit denen an den Positionen (j , i) identisch und damit ist die Matrix also symmetrisch zur Hauptdiagonale.

[ Was bedeutet eine Eintrag an der Position (i , i) für den Graphen ? ]

Adjazenzliste

Datentyp VERKETTETE LISTE

Zu jeder Ecke des Graphen wird jeweils eine Liste der benachbarten Ecken gespeichert.

Bei durchnummerierten Ecken kann man sich dabei die Verwaltung der Nummern sparen und hat nur in richtiger Reihenfolge die Listen der Nachfolgeecken zu speichern.

Schwieriger als im Fall der Adjazenzmatrix ist es bei der Adjazenzliste festzustellen, ob der Graph ungerichtet ist.

In diesem Fall ist es daher sinnvoll, beim Aufbau der Datenstruktur

entweder oder

Kantenliste

Während bei den beiden vorher angegebenen Datenstrukturen Ecken gespeichert werden, werden in einer Kantenliste die Kanten selbst gespeichert. In diesem Fall ist es natürlich einfach, eine Kante zu finden, während es schwieriger wird alle von einer Ecke ausgehenden Kanten zu finden.

Bewertete Graphen

Zu einer Kante ist jeweils noch ein Wert gespeichert, der diese Kante im Vergleich zu den anderen bewertet. ( Dazu später mehr. )

Implizite Speicherung

Bei einer impliziten Speicherung ist die Datenstruktur abhängig von einer speziellen Modellierung sozusagen versteckt gespeichert. Das Ziel ist eine möglichst effiziente Speicherung oder ein möglichst effizienter Zugriff.

Lösungsansatz: Vorher nachdenken, ob es bei dem speziellen Problem einfacher geht !

Meist wird man bei allgemeinen Suchproblemen eine Repräsentation des Graphen im Programmtext vergeblich suchen: Knoten und Kanten werden sozusagen während des Programmlaufs erst berechnet oder anderweitig bestimmt und das auch nur, soweit sie für die Suche erforderlich sind.