Der Graph als abstrakter Datentyp

In diesem Beitrag werden wir uns mit Graphen als abstrakte Datentypen beschäftigen. Ein Graph besteht aus einer Menge von Knoten und Kanten. Ein Knoten speichert die eigentlichen Daten und wird auch „Ecke” oder „Vertex” genannt. Eine Kante verbindet Knoten mit einander und wird auch „Edge” genannt.

Ein einfacher Graph könnte beispielsweise folgendermaßen definiert sein. Dieser Graph ist zusammenhängend, ungerichtet und besitzt demnach auch keine Zyklen.

Knoten: 1, 2,3, 4, 5,6

Kanten:

  • 1,2
  • 2,3
  • 3,6
  • 6,6
  • 3,4
  • 4,5
  • 3,5

Verketteter Graph

Die Implementierung eines Verketteten Graphen gleicht der einer Implementierung für einen verketteten Baum. Es existiert – anders als bei einer Baumstruktur – kein definierter Startknoten. Außerdem gibt es keine Beschränkung in der Anzahl von Elternknoten. Dabei entsteht ein Sogenannter gerichteter Graph. Dies wurde in der Abbildung durch grüne Pfeile ersichtlich gemacht. 

Ein einfacher verketteter gerichteter Graph.
Ein einfacher verketteter gerichteter Graph.

Der Unterschied zwischen einem gerichteten und ungerichteten Graphen liegt in seiner Kantendefinition. Bei einem gerichteten haben diese eine Richtungsangabe. Die Kanten (1, 2) und (2, 1) sind daher unterschiedliche Kanten, da sie jeweils in eine andere Richtung zeigen. Anders sieht dies bei einem ungerichteten Graphen aus, denn durch die fehlende Richtungsangabe sind die Kanten (1,2) und (2,1) gleich und es gilt:

∀ a,b ∈ V:(a,b) ∈ E →(b,a) ∈ E

Zyklen

Ein zyklischer Graph.
Ein zyklischer Graph.

Zyklen beschreiben einen Pfad von einem Knoten zu sich selbst. In einem ungerichteten Graph darf jede Kante deshalb nur in eine Richtung auf diesem Pfad auftauchen.

 

Einen Graph, der keine Zyklen enthält, nennt man azyklischer Graph.

 

 

Einen Graph ist zusammenhängend, wenn zwischen jedem Paar von Knoten mindestens eine Kante existiert. Zusätzlich unterscheidet man bei einem gerichteten Graphen zwischen schwach und stark Zusammenhängend, je nach dem, ob eine Kante in beide Richtungen existiert oder nur in eine Richtung.

Ein Beispiel für einen nicht zusammenhängenden Graphen, welcher in Zusammenhangs-Komponenten zerfällt.
Ein Beispiel für einen nicht zusammenhängenden Graphen, welcher in Zusammenhangs-Komponenten zerfällt.

 

Merke: Bei einer Tiefen- oder Breitensuche eines zyklischen Graphen entsteht eine Endlosschleife, die man nur durch dynamisches Programmieren umgehen kann. Dabei merkt man sich die bereits besuchten Knoten und überspringt diese gegebenenfalls.

 

Kommentare

Zusammenfassung
Der Graph als abstrakter Datentyp
Artikeltitel
Der Graph als abstrakter Datentyp
Beschreibung
In diesem Beitrag werden wir uns mit Graphen als abstrakte Datentypen beschäftigen
Autor

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

E-Mail-Benachrichtigung bei weiteren Kommentaren.
Auch möglich: Abo ohne Kommentar.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.

Pin It on Pinterest

Durch die weitere Nutzung der Seite stimmst du der Verwendung von Cookies zu. Weitere Informationen

Die Cookie-Einstellungen auf dieser Website sind auf "Cookies zulassen" eingestellt, um das beste Surferlebnis zu ermöglichen. Wenn du diese Website ohne Änderung der Cookie-Einstellungen verwendest oder auf "Akzeptieren" klickst, erklärst du sich damit einverstanden.

Schließen