Datenstrukturen

Ein Graph ist eine Menge von Knoten und Kanten. Eine Kante ist ein geordnetes Paar von Knoten und hat eventuell noch ein Gewicht. Um die Sache zu vereinfachen werden die Knoten von 1 bis n durchnumeriert. Zur Speicherung der Knoten genügt deren Anzahl. Bei den Kanten muss etwas mehr Aufwand betrieben werden.

Kantenliste

Die einfachste Variante ist die Kantenliste. Dabei speichert man zu jeder Kante, deren Start- und Endknoten (als Index).


  long *startnode = (long *) calloc(edgecount, sizeof(long));
  long *endnode   = (long *) calloc(edgecount, sizeof(long));
  long *weight    = (long *) calloc(edgecount, sizeof(long));

Dazu muss natürliuch die Anzahl der Kanten bekannt sein. Ist dies nicht der Fall, ist es möglich die Felder mit realloc zu erweitern, oder man verwendet eine verkettete Liste.


  struct LinkedFullEdge {
    long startnode;
    long endnode
    long weight;
    struct LinkedFullEdge *next;
  };

Häufig arbeiten Algorithmen mit den Kanten, die von einem bestimmten Knoten zu anderen führen. Dazu müsste die gesamte Liste durchsucht werden.

Adjazenzliste

Eine etwas abgewandelte Variante der verketteten Kantenliste ist die Adjazenzliste. Dabei wird zu jedem Knoten eine Kantenliste der zu diesem Knoten inzidenten Kanten gespeichert. Dies hat zum einen den Vorteil, das die lineare Suche der ersten Variante entfällt. Zum anderen muss der Startknoten nicht gespeichert werden, da dieser bei allen Kanten einer Liste identisch ist.


  struct LinkedEdge {
    long endnode
    long weight;
    struct LinkedEdge *next;
  };

  struct AdjazenzList {
    long nodecount;
    long edgecount;
    struct LinkedEdge **edges;
  };

Dann ist zum Beispiel list->edges[k] die Liste aller Kanten, die vom Knoten k abgehen. Umgekehrt können nicht direkt alle Kanten bestimmt werden, die zu einem gewählten Knoten hinführen.

Adjazenzmatrix

Dieses Problem löst die Anjazenzmatrix. Dabei ist zum Beispiel a[i][j] == 1 falls es eine Kante von Knoten i nach Knoten j gibt. Das funktioniert natürlich nur für schlichte Graphen, d.h. es darf keine parallelen bzw. doppelten Kanten geben. Einfache Schlingen (Kanten von i nach i) sind möglich).
Falls der Graph ungerichtet ist, ergibt sich eine symmetrische Matrix. Dann muss nur die obere Dreiecksmatrix gespeichert werden, was den Speicherbedarf halbiert auf Kosten einer leicht erhöhten Rechenzeit. Bei einem schlichten Graphen ohne Schlingen kann auch die Hauptdiagonale entfernt werden. Der Speicherbedarf ist trotzdem quadratisch zur Knotenanzahl, unabhängig wieviele Kanten der Graph besitzt.
Bei einem gewichteten Graphen, kann auch gleich das Gewicht in der Matrix abgelegt werden. Man benötigt nur eine Konstante, die angibt, dass eine Kante nicht existiert.

Zurück zur Hauptseite Computerorientierte Mathematik.


Erstellt von Markus Durzinsky, aktualisiert 2003-10-25
Für Fragen, Probleme oder Anregungen stehe ich gerne zur Verfügung