In diesem Tutorial erfahren Sie, was eine Diagrammdatenstruktur ist. Außerdem finden Sie Darstellungen eines Diagramms.
Eine Diagrammdatenstruktur ist eine Sammlung von Knoten, die Daten enthalten und mit anderen Knoten verbunden sind.
Versuchen wir dies anhand eines Beispiels zu verstehen. Auf Facebook ist alles ein Knoten. Dazu gehören Benutzer, Foto, Album, Ereignis, Gruppe, Seite, Kommentar, Story, Video, Link, Notiz … alles, was Daten enthält, ist ein Knoten.
Jede Beziehung ist eine Kante von einem Knoten zum anderen. Unabhängig davon, ob Sie ein Foto veröffentlichen, einer Gruppe beitreten, z. B. einer Seite usw., wird für diese Beziehung ein neuer Rand erstellt.
Beispiel für eine Graphdatenstruktur
Facebook ist dann eine Sammlung dieser Knoten und Kanten. Dies liegt daran, dass Facebook eine Grafikdatenstruktur verwendet, um seine Daten zu speichern.
Genauer gesagt ist ein Graph eine Datenstruktur (V, E), aus der besteht
- Eine Sammlung von Eckpunkten V.
- Eine Sammlung von Kanten E, dargestellt als geordnete Eckpunktpaare (u, v)
Eckpunkte und Kanten
In der Grafik
V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)
Graph Terminologie
- Adjazenz : Ein Scheitelpunkt wird als benachbart zu einem anderen Scheitelpunkt bezeichnet, wenn eine Kante sie verbindet. Die Eckpunkte 2 und 3 sind nicht benachbart, da sich zwischen ihnen keine Kante befindet.
- Pfad : Eine Folge von Kanten, mit der Sie von Scheitelpunkt A zu Scheitelpunkt B wechseln können, wird als Pfad bezeichnet. 0-1, 1-2 und 0-2 sind Pfade von Scheitelpunkt 0 zu Scheitelpunkt 2.
- Gerichteter Graph : Ein Graph, in dem eine Kante (u, v) nicht unbedingt bedeutet, dass es auch eine Kante (v, u) gibt. Die Kanten in einem solchen Diagramm werden durch Pfeile dargestellt, um die Richtung der Kante anzuzeigen.
Diagrammdarstellung
Diagramme werden üblicherweise auf zwei Arten dargestellt:
1. Adjazenzmatrix
Eine Adjazenzmatrix ist ein 2D-Array von V x V-Eckpunkten. Jede Zeile und Spalte repräsentiert einen Scheitelpunkt.
Wenn der Wert eines Elements a(i)(j)1 ist, bedeutet dies, dass es eine Kante gibt, die den Scheitelpunkt i und den Scheitelpunkt j verbindet.
Die Adjazenzmatrix für das oben erstellte Diagramm lautet
Graph Adjazenzmatrix
Da es sich um einen ungerichteten Graphen handelt, müssen wir für Kante (0,2) auch Kante (2,0) markieren. die Adjazenzmatrix symmetrisch zur Diagonale machen.
Die Kantensuche (Überprüfung, ob eine Kante zwischen Scheitelpunkt A und Scheitelpunkt B vorhanden ist) ist in der Adjazenzmatrixdarstellung extrem schnell, aber wir müssen Platz für jede mögliche Verbindung zwischen allen Scheitelpunkten (V x V) reservieren, sodass mehr Platz benötigt wird.
2. Adjazenzliste
Eine Adjazenzliste repräsentiert ein Diagramm als Array verknüpfter Listen.
Der Index des Arrays repräsentiert einen Scheitelpunkt und jedes Element in seiner verknüpften Liste repräsentiert die anderen Scheitelpunkte, die mit dem Scheitelpunkt eine Kante bilden.
Die Adjazenzliste für das Diagramm, das wir im ersten Beispiel erstellt haben, lautet wie folgt:
Darstellung der Adjazenzliste
Eine Adjazenzliste ist hinsichtlich der Speicherung effizient, da nur die Werte für die Kanten gespeichert werden müssen. Für ein Diagramm mit Millionen von Eckpunkten kann dies viel Platz sparen.
Diagrammoperationen
Die häufigsten Diagrammoperationen sind:
- Überprüfen Sie, ob das Element im Diagramm vorhanden ist
- Graph Traversal
- Fügen Sie dem Diagramm Elemente (Scheitelpunkt, Kanten) hinzu
- Finden des Pfades von einem Scheitelpunkt zum anderen
