Java >> Java Tutorial >  >> Java

Einführung in Diagramme

In meinem vorherigen Artikel habe ich über Hashtables gesprochen. Ich werde in diesem Beitrag eine weitere Datenstruktur besprechen, und es ist wahrscheinlich eine der wichtigsten Datenstrukturen überhaupt, und das sind Graphs .

Natürlich sind unsere aktuellen Webtechnologien stark von Graphen abhängig. Google, Facebook oder LinkedIn oder jede andere Social-Media-Plattform, die Benutzer enthält, verwendet Grafiken als Datenstruktur. Graphen sind also die häufigste Datenstruktur zur Lösung von Problemen im Zusammenhang mit der Ermittlung der Entfernung zwischen zwei Knoten ODER des kürzesten Pfads von Ort A zu Ort B.

Daher sind wir bei sozialen Netzwerken an sechs Freiheitsgrade gewöhnt, in solchen Fällen können wir Diagramme verwenden, um herauszufinden, wie viele Grad es braucht, um zwei Knoten im sozialen Netzwerk zu verbinden. Bei Netzwerken verwenden die meisten Diagramme, um den schnellsten Weg zur Bereitstellung der Antwort zu finden.

Wie erklärt man 5 Jahren Graphen?

Das einfachste Beispiel, das man einem Kind geben kann, um Graphen zu erklären, ist, sich Stadt A und Stadt B auf einer Karte anzusehen. Verwenden Sie jetzt die Straße, die diese beiden Städte verbindet.

Stadt A – hat Bananen, Orangen, Stadt B – hat Äpfel und Stadt C – hat Wassermelonen.

Nun auf der Karte, wenn wir von Stadt A nach Stadt B reisen, welche mögliche Route wir nehmen können und welche Informationen wir austauschen können. Stadt A und Stadt B können einander Äpfel, Bananen, Orangen übertragen. Sobald Stadt B Bananen und Orangen bekommt, kann sie diese auf andere benachbarte Städte übertragen.

Kurz gesagt, wir verbinden die Knoten (Scheitelpunkte) der Städte A und B durch eine Straße (Kante), während wir die Produkte austauschen, für die diese beiden Städte bekannt sind.

Graphs-Datenstruktur

In diesem Beitrag werden wir Graphen aus der Java-Perspektive besprechen. Diagramme ermöglichen die Darstellung realer Beziehungen zwischen verschiedenen Datentypen. Es gibt zwei wichtige Aspekte für die grafische Darstellung:

  • Vertices (Knoten) – Knoten stellen die Punkte eines Graphen dar, an denen der Graph verbunden ist. Knoten speichern die Daten oder Datenpunkte.
  • Kanten – Kanten repräsentieren die Beziehung zwischen verschiedenen Knoten. Kanten können Gewicht oder Kosten haben.

Es gibt jedoch keinen Startknoten oder Endknoten im Diagramm. Ein Graph kann zyklisch oder azyklisch sein. Zusammenfassend können Kanten gerichtet oder ungerichtet sein, die gerichtete oder ungerichtete Graphen hervorbringen.

Beispielsweise werden Kanten im Allgemeinen in Form einer Menge geordneter Paare wie in (x,y) dargestellt – es gibt eine Kante von Knoten x zu Knoten y. Daher kann (x,y) von (y,x) verschieden sein, insbesondere im gerichteten Graphen.

Darstellungen von Grafiken

A. Adjazenzmatrix –

Dies ist ein zweidimensionales Array der Größe n*n, wobei n die Anzahl der Knoten im Diagramm ist. adj[][] ist die übliche Art, diese Matrix darzustellen. Also wenn adj[i][j] = 1 stellt er eine Kante zwischen Knoten i und Knoten j dar. Die Adjazenzmatrix für einen ungerichteten Graphen ist symmetrisch. Wenn ich nun den oben in der Abbildung gezeigten Graphen darstellen muss, werde ich ihn wie folgt darstellen:

                A               B             C        G         E
               A                 0               1             0         1         0
               B                1              0             1         0         1
               C                 0              1             0         0         1
               G                1              0             0         0         1
               E                 0              1             1         1         0

 B. Adjazenzliste –

In ähnlicher Weise wird ein Array von Listen verwendet. Die Größe des Arrays entspricht der Anzahl der Knoten im Diagramm. Also zeigt arr[i] die Liste der Scheitelpunkte an, die an den Knoten i angrenzen.

Operationen auf den Graphen

Es gibt allgemeine Operationen, die wir oft verwenden werden. Ebenso bietet graph als Datenstruktur die folgenden Operationen:

Ergänzungen

addNode – Knoten im bestehenden Diagramm hinzufügen

addEdge – Füge im bestehenden Graphen eine Kante zwischen zwei Knoten hinzu

Entfernung

removeNode – Entfernen Sie einen Knoten aus dem bestehenden Diagramm

removeEdge – Eine Kante zwischen zwei Knoten aus dem Graphen entfernen

Suchen

contains – Finden Sie heraus, ob der Graph den angegebenen Knoten enthält

hasEdge – Finde heraus, ob es eine Kante zwischen gegebenen zwei Knoten gibt

Zeitliche und räumliche Komplexität von Operationen auf Graphen

Vor allem wäre ein Beitrag unvollständig, wenn ich nicht über die Komplexität von Operationen an der Graph-Datenstruktur sprechen würde. Grundsätzlich hängt dies wirklich davon ab, welche Darstellungen Sie für den Graphen verwenden. Bei Adjazenzmatrix sind Additions- und Entfernungsoperationen O(1) Operationen. Während Suchoperationen wie contains und hasEdge sind auch O(1) Operationen. Außerdem beträgt die Raumkomplexität für die Adjazenzmatrix O(n*n) .

Bei Adjazenzliste sind Zusätze O(1) und das Entfernen eines Knotens ist O(n) Operation, Entfernung einer Kante ist O(1) . Daher sind Suchvorgänge gleichermaßen O(1)

Schlussfolgerung

Abschließend habe ich die Grundlagen des Graphen als Datenstruktur gezeigt. Der Graph ist eine Datenstruktur, die Knoten und Kanten enthält. Außerdem verfügt es über Operationen wie Hinzufügen, Entfernen und Suchen. In zukünftigen Beiträgen werde ich über die Implementierung von Depth First Search sprechen und Breadth First Search in der Grafik. Danach werden wir einige echte Probleme mit dieser Datenstruktur lösen. Graph ist vor allem eine wichtige Datenstruktur.

Referenzen

  1. Einführung in Graphen – Graphen
  2. Graph als Datenstruktur – Graph als Datenstruktur

Java-Tag