Unsere Datenschutzrichtlinie wird in Kürze aktualisiert. Bitte sehen Sie sich die Vorschau an.

Grundlagen der Programmierung: Datenstrukturen

Graphen

Testen Sie unsere 2016 Kurse

10 Tage kostenlos!

Jetzt testen Alle Abonnements anzeigen
Graphen sind Datenstrukturen, die nur indirekt in anderen Datenstrukturen implementiert sind. Sie eignen sich insbesondere zur Darstellung von netzwerkartigen Strukturen und bestehen aus Knoten (vertices) und Kanten (edges).

Transkript

Graphen sind eine weitere Datenstruktur, die wir uns nur ganz am Rande ansehen werden. Graphen sind ähnlich wie binäre Suchbäume oder auch Heaps Datenstrukturen, die eher nur indirekt implementiert werden. Sie treten also im Zusammenhang mit anderen Datenstrukturen auf. Was am Anfang vielleicht noch wichtig ist zu erwähnen, ist dass Sie diese Graphen nicht mit den optischen Graphen verwechseln sollten. Hier geht's nicht um eine visuelle Darstellung von irgendwas, sondern es geht nach wie vor um eine Datenstruktur. Wir haben ja schon diverse Datenstrukturen kennengelernt, die alle gewisse Einschränkungen beinhalten. Wenn wir uns zum Beispiel eine verlinkte Liste anschauen, so haben wir einzelne Objekte, die miteinander verbunden sind, die aber nur in sehr beschränkter Weise miteinander verbunden sind. Ähnlich ist es mit der Baumstruktur. Ich habe da Knoten, die Knoten führen zu Kindknoten, die Kindknoten haben wieder Kindknoten. Aber es gibt eine ganze Reihe von Gesetzmäßigkeiten, die hier noch weiter zum Tragen kommen. Zum Beispiel, dass ein Kindknoten nur einen Elternknoten haben kann. Dass in unserem Fall die Elternknoten nur je zwei Kindknoten haben können. Dass die Kindknoten, also die Geschwister, untereinander nicht verbunden sein können. Das alles sind Einschränkungen von der Baumstruktur, die bei Graphen so nicht zu finden sind. Graphen haben zwar auch einzelne Objekte. Diese einzelnen Objekte können aber wahllos miteinander verbunden werden. Da gibt's nicht die Beschränkung, dass ich nur zwei Kindelemente haben könnte. Sondern die Objekte sind zueinander gleichwertig und kann sich ein Objekt durchaus mit mehreren Objekten verbinden. Im Zusammenhang mit einem Beispiel: Wir könnten dieses Szenario zum Beispiel einsetzen, um ein soziales Netzwerk zu beschreiben. Da wird dann ausgehend von einer beliebigen Person deren Verknüpfung mit anderen Personen angesehen und wie die dann wieder untereinander verbunden sind. Da merken Sie eben diese Gewichtung eines Graphen. Bei einem Graphen haben Objekte von sich aus keine spezielle Gewichtung. Aber wir müssen uns auch ein, zwei Details ansehen, was es mit der Terminologie auf sich hat. Was normalerweise als Knoten bekannt ist, wird im Zusammenhang mit Graphen als Ecken bezeichnet: vertices. Und die Verbindungen zwischen diesen Ecken werden Kanten genannt. Im Englischen also: edges. Das heißt, Graphen bestehen aus Ecken und Kanten. Der Einsatz von Graphen ist sehr vielseitig. Was aber vielleicht vorher noch wichtig ist zu klären ist, dass es unterschiedliche Graphentypen gibt. Es gibt gerichtete und ungerichtete Graphen. Ein gerichteter Graph ist daran zu erkennen, dass die Kanten eine bestimmte Richtung haben. Die Kanten sind hin zu einer Ecke gerichtet. Im Unterschied zu ungerichteten Graphen, wo es keine besondere Gewichtung in eine bestimmte Richtung gibt. Und neben gerichteten und ungerichteten Graphen gibt es auch noch gewichtete Graphen. Gewichtete Graphen sind Graphen, wo die Kanten spezielle Gewichtungen mitbekommen. Nehmen wir hier zum Beispiel einmal eine Verbindung zwischen einzelnen Städten. Da würde dann die Gewichtung zum Beispiel für die Entfernung stehen. Auf diese Weise können Routen berechnet werden. Welche Route dann insgesamt am besten ist, welche am kürzesten ist oder welche am schnellsten erreicht werden kann. Genau dafür werden Graphen auch eingesetzt. Graphen werden dafür eingesetzt, dass sie diese Form von Zusammenhängen gut herausarbeiten können. Die eingebaute Graphen-Unterstützung ist vorrangig einmal nicht gegeben. Es gibt in keiner der großen, gängigen Sprachen eine direkte Sprachunterstützung für etwas wie einen Graphen. Aber Graphen sind eigentlich in sehr vielen Teilbereichen im Einsatz. Eine verlinkte Liste zum Beispiel ist in Wirklichkeit ein Graph. Und zwar ein gerichteter Graph. Das heißt, bei der verlinkten Liste habe ich immer einen Eckpunkt, der mit seiner Kante zum nächsten Eckpunkt zeigt. Oder auch bei einer Baumstruktur. Eine Baumstruktur ist eindeutig ein Graph, ebenfalls ein gerichteter Graph. Ich habe Elternelemente, die auf ihre Kindelemente verweisen. Ebenso verhält es sich bei Heaps. Das heißt, Graphen sind von ihrer Datenstruktur her grundlegender Teil von anderen Datenstrukturen. Auch wenn sie bei den einzelnen Sprachen keine direkte Unterstützung haben, so kommen sie dort doch permanent in Form der anderen Datenstrukturen zum Einsatz.

Grundlagen der Programmierung: Datenstrukturen

Erhalten Sieeinen klaren Eindruck von Datenstrukturen und deren Eigenheiten und verstehen, wie Sie diese am besten einsetzen können – ganz unabhängig von den einzelnen Programmiersprachen.

2 Std. 51 min (29 Videos)
Derzeit sind keine Feedbacks vorhanden...
 

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!