Diagrammdatenstruktur und Algorithms (Beispiel)

Was ist ein Diagramm in der Datenstruktur?

Ein Graph ist eine nichtlineare Datenstruktur, die aus Knoten und Kanten besteht, wobei die Knoten die Informationen oder Daten enthalten und die Kanten als Verbindung zwischen zwei Knoten fungieren.

Es dient zur Lösung realer Probleme, wie beispielsweise der Ermittlung der optimalen Route zum Zielort oder der Routenplanung für Telekommunikations- und soziale Netzwerke. Benutzer werden als Knoten im Graphen betrachtet, und die Verbindungen zwischen den Benutzern werden durch die Linien (Draht) dargestellt.

Wenn Kanten als E und Scheitelpunkte als V dargestellt werden, kann der Graph G als Menge von Scheitelpunkten und Kanten geschrieben werden, z G (V, E).

Beispiel für ein Diagramm in der Datenstruktur

Hier ist ein einfaches Beispiel für eine Graphdatenstruktur:

Es handelt sich um einen einfachen ungerichteten Graphen (eine Art von Graph). Die Menge der Knoten ist: {A, B, C, D, E, F}. Zwei Knoten bilden eine Kante. Beispielsweise sind A und B durch eine Kante verbunden. A und F hingegen sind durch keine Kante verbunden.

Diagrammterminologien in der Datenstruktur

Im Folgenden werden einige wichtige Begriffe erläutert, die in der Graphdatenstruktur verwendet werden:

Bedingungen	Beschreibung
Scheitel	Jedes Datenelement wird als Knoten oder Eckpunkt bezeichnet. In der obigen Abbildung sind A, B, C, D und E die Eckpunkte.
Kante (Bogen)	Verbindungen zwischen zwei Knoten oder Eckpunkten werden als Kante (Bogen) bezeichnet. Sie hat zwei Enden und wird als (Startknoten, Endknoten) dargestellt.
Ungerichtete Kante	Es handelt sich um eine bidirektionale Kante.
Gerichtete Kante	Es handelt sich um eine unidirektionale Kante.
Beschwerter Rand	Eine Kante mit einem Wert darauf.
Grad	In einem Graphen wird die Anzahl der Kanten, die mit einem Knoten verbunden sind, als Grad bezeichnet.
Grad	Die Gesamtzahl der eingehenden Kanten, die mit einem Scheitelpunkt verbunden sind.
Abschluss	Die Gesamtzahl der ausgehenden Kanten, die mit einem Scheitelpunkt verbunden sind.
Selbstschleife	Eine Kante heißt Selbstschleife, wenn ihre beiden Endpunkte zusammenfallen.
Nachbarschaft	Knotenpunkte gelten als benachbart, wenn eine Kante zwischen ihnen besteht.

Arten von Diagrammen in der Datenstruktur

Hier ist die Liste der häufigsten Arten von Diagrammen in der Datenstruktur:

• Gerichteter Graph
• Ungerichteter Graph
• Gewichtetes Diagramm
• Bidirektionaler Graph
• Unendliche Grafik
• Nulldiagramm
• Trivialer Graph
• Multi-Graph
• Vollständige Grafik
• Verbundenes Diagramm
• Zyklischer Graph
• Gerichteter azyklischer Graph (DAG)
• Zyklusdiagramm
• Zweiteiliger Graph
• Euler-Diagramm
• Hamilton-Diagramm

Wie stellt man einen Graphen in einer Datenstruktur dar?

Ein Graph wird üblicherweise mithilfe einer von zwei Darstellungsformen im Speicher abgelegt. Die Wahl der Darstellungsform beeinflusst den Speicherbedarf des Graphen und die Ausführungsgeschwindigkeit gängiger Operationen.

• Adjazenzmatrix: Ein zweidimensionales V × V-Array, in dem Zelle [i][j] den Wert 1 (oder das Kantengewicht) annimmt, wenn eine Kante zwischen Knoten i und Knoten j existiert, und ansonsten den Wert 0. Es ermöglicht die Kantensuche in konstanter Zeit (O(1)), benötigt aber O(V²) Speicherplatz und eignet sich daher am besten für dichte Graphen.
• Nachbarschaftsliste: Ein Array von Listen, wobei jeder Knoten eine Liste seiner Nachbarknoten speichert. Es benötigt O(V + E) Speicherplatz und ist effizient für dünn besetzte Graphen, weshalb es in den meisten realen Graphen verwendet wird.

Mehr dazu können Sie in der Adjazenzliste und Matrixdarstellung eines Graphen Tutorial.

Anwendungen der Graphdatenstruktur

Graphen haben viele Anwendungsfälle. Zahlreiche Algorithmen nutzen Graphen. Hier einige Beispiele für die Verwendung von Graphen:

• Google Karten verwenden Graphen, um die Schnittpunkte zweier Straßen zu finden und die Entfernung zwischen zwei Orten zu berechnen. Zum Beispiel: Dijkstra, um die kürzeste Entfernung zwischen Start- und Zielort zu ermitteln.
• Facebook verwendet Graphen, um die gemeinsamen Freunde der Nutzer zu finden. Der Algorithmus betrachtet jeden Nutzer als Knotenpunkt eines Graphen.
• Zur Ressourcenzuweisung wird ein DAG (gerichteter azyklischer Graph) verwendet. Dieser prüft die Abhängigkeiten der Ressourcen.
• Das Google Suchmaschinen verwenden Diagramme, um die Rangfolge von Webseiten zu erstellen.
• Eine Karteping Das Gerät verwendet die Graphdatenstruktur.
• A Router und sein Protokoll verwendet den Graphen, um den Pfad zum Ziel zu ermitteln.

Häufig gestellte Fragen