Datenstruktur - Diagrammdatenstruktur
Ein Diagramm ist eine bildliche Darstellung einer Gruppe von Objekten, bei denen einige Objektpaare durch Verknüpfungen verbunden sind. Die miteinander verbundenen Objekte werden durch Punkte dargestellt, die als bezeichnet werdenverticesund die Verknüpfungen, die die Eckpunkte verbinden, werden aufgerufen edges.
Formal ist ein Graph ein Paar von Mengen (V, E), wo V ist die Menge der Eckpunkte und Eist die Menge der Kanten, die die Eckpunktepaare verbinden. Schauen Sie sich die folgende Grafik an -
In der obigen Grafik
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Diagrammdatenstruktur
Mathematische Graphen können in Datenstruktur dargestellt werden. Wir können einen Graphen mit einem Array von Eckpunkten und einem zweidimensionalen Array von Kanten darstellen. Bevor wir fortfahren, machen wir uns mit einigen wichtigen Begriffen vertraut -
Vertex- Jeder Knoten des Diagramms wird als Scheitelpunkt dargestellt. Im folgenden Beispiel repräsentiert der beschriftete Kreis Scheitelpunkte. Somit sind A bis G Eckpunkte. Wir können sie mit einem Array darstellen, wie im folgenden Bild gezeigt. Hier kann A durch Index 0 identifiziert werden. B kann unter Verwendung von Index 1 usw. identifiziert werden.
Edge- Kante repräsentiert einen Pfad zwischen zwei Eckpunkten oder eine Linie zwischen zwei Eckpunkten. Im folgenden Beispiel repräsentieren die Linien von A nach B, B nach C usw. Kanten. Wir können ein zweidimensionales Array verwenden, um ein Array darzustellen, wie im folgenden Bild gezeigt. Hier kann AB als 1 in Zeile 0, Spalte 1, BC als 1 in Zeile 1, Spalte 2 usw. dargestellt werden, wobei andere Kombinationen als 0 beibehalten werden.
Adjacency- Zwei Knoten oder Eckpunkte sind benachbart, wenn sie über eine Kante miteinander verbunden sind. Im folgenden Beispiel ist B neben A, C ist neben B und so weiter.
Path- Der Pfad repräsentiert eine Folge von Kanten zwischen den beiden Eckpunkten. Im folgenden Beispiel repräsentiert ABCD einen Pfad von A nach D.
Grundoperationen
Es folgen grundlegende primäre Operationen eines Graphen -
Add Vertex - Fügt dem Diagramm einen Scheitelpunkt hinzu.
Add Edge - Fügt eine Kante zwischen den beiden Eckpunkten des Diagramms hinzu.
Display Vertex - Zeigt einen Scheitelpunkt des Diagramms an.
Um mehr über Graph zu erfahren, lesen Sie bitte das Graph Theory Tutorial . In den kommenden Kapiteln erfahren Sie, wie Sie ein Diagramm durchlaufen.