Die Graph-Datenstruktur ist ein Satz 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, Fotos, Alben, Ereignisse, Gruppen, Seiten, Kommentare, Geschichten, Videos, Links, Notizen ... alles, was Daten enthält, ist ein Knoten.
Jede Relation ist eine Kante von einem Knoten zum anderen. Egal, ob Sie ein Foto posten, einer Gruppe wie einer Seite beitreten usw. Für diese Beziehungen wird ein neuer Vorteil geschaffen.
Dann ist das ganze Facebook eine Ansammlung von Knoten und Kanten. Dies liegt daran, dass Facebook eine Graph-Datenstruktur verwendet, um seine Daten zu speichern.
Genauer gesagt ist graph eine Datenstruktur (V, E), die besteht aus:
- Scheitelpunktsammlung V.
- Eine Menge von Kanten E, dargestellt als geordnete Knotenpaare (u, v).
Graf eingeführt
V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}
Terminologiediagramm
Nachbarschaft.
Ein Knoten wird als benachbart zu einem anderen Knoten bezeichnet, wenn es eine Kante gibt, die sie verbindet.
Die Knoten 2 und 3 sind nicht benachbart, da zwischen ihnen keine Kante liegt.Pfad.
Die Folge von Kanten, die es Ihnen ermöglicht, von Knoten A nach Knoten B zu gelangen, wird als Pfad bezeichnet.
0-1, 1-2 und 0-2 sind Pfade von Knoten 0 zu Knoten 2.Orientierte Grafik.
Ein Graph, der eine Kante (u, v) hat, bedeutet nicht zwangsläufig, dass es auch eine Kante (v, u) gibt. Kanten in einem solchen Diagramm werden durch Pfeile dargestellt, um die Richtung der Kante anzuzeigen.
Grafikdarstellungsmethoden
Diagramme werden normalerweise auf zwei Arten dargestellt:
eines. Nachbarschaftsmatrix
Adjazenzmatrix ist ein zweidimensionales (2D) Array von V x V Scheitelpunkten. Jede Zeile und Spalte repräsentiert einen Scheitelpunkt.
Wenn der Wert eines Elements von a[i][j] 1 ist, bedeutet dies, dass es eine Kante gibt, die Knoten i und Knoten j verbindet.
Die Adjazenzmatrix für den oben erstellten Graphen.
Da dies ein ungerichteter Graph ist, müssen wir für Kante (0,2) auch Kante (2,0) markieren, wodurch die Adjazenzmatrix symmetrisch zur Diagonalen wird.
Die Kantensuche (Prüfung, ob es eine Kante zwischen Scheitelpunkt A und Scheitelpunkt B gibt) ist in der Adjazenzmatrixdarstellung extrem schnell, aber wir müssen Platz für jede mögliche Verbindung zwischen allen Scheitelpunkten (V x V) reservieren, also braucht es mehr Platz.
2. Nachbarschaftsliste
Adjazenzliste ist ein Diagramm in Form eines Arrays aus verknüpften Listen.
Der Array-Index stellt einen Scheitelpunkt dar, und jedes Element in seiner verknüpften Liste stellt andere Scheitelpunkte dar, die mit dem Scheitelpunkt eine Kante bilden.
Die Adjazenzliste für den Graphen, den wir im ersten Beispiel erstellt haben, sieht folgendermaßen aus:
Die Adjazenzliste ist speichereffizient, da wir nur Werte für Kanten speichern müssen. Für einen Graphen mit Millionen von Scheitelpunkten kann dies eine Menge Platzersparnis bedeuten.
Operationen auf Diagrammen
Die häufigsten Graphoperationen sind:
- Überprüfen Sie, ob das Element in der Grafik vorhanden ist.
- Graphdurchlauf.
- Fügen Sie dem Diagramm Elemente (Eckpunkte, Kanten) hinzu.
- Finden eines Pfades von einem Scheitelpunkt zum anderen.
