Diagrammdatenstruktur und Algorithms (Beispiel)
Sarah Chen
Was ist ein Diagramm in der Datenstruktur?
Ein Graph ist eine nichtlineare Datenstruktur, die aus Scheitelpunkten und Kanten besteht, wobei Scheitelpunkte die Informationen oder Daten enthalten und die Kanten als Verbindung zwischen Scheitelpunktpaaren fungieren.
Es wird verwendet, um echte Wortprobleme zu lösen, beispielsweise die Suche nach der besten Route zum Zielort und der Route für Telekommunikation und soziale Netzwerke. Benutzer werden im Diagramm als Knoten betrachtet und die Drähte sind die Kanten, die die Benutzer verbinden.
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 die Datenstruktur eines Diagramms:
Es ist ein einfacher ungerichteter Graph (eine Art von Graph). Hier ist die Menge der Scheitelpunkte: {A, B, C,D,E,F}. Zwei Scheitelpunkte erzeugen eine Kante. Beispielsweise sind A und B mit einer Kante verbunden. A und F sind jedoch nicht mit Kanten verknüpft.
Diagrammterminologien in der Datenstruktur
Im Folgenden sind einige wichtige Begriffe aufgeführt, die in der Graphdatenstruktur verwendet werden:
| Bedingungen | Beschreibung |
|---|---|
| Scheitel | Jedes Datenelement wird als Scheitelpunkt oder Knoten bezeichnet. Im obigen Bild sind A, B, C, D und E die Eckpunkte. |
| Kante (Bogen) | Verbindungsverbindungen zwischen zwei Knoten oder Eckpunkten werden als Kante (Bogen) bezeichnet. Es hat zwei Enden und wird als (startingVertex, endingVertex) dargestellt. |
| Ungerichtete Kante | Es handelt sich um eine bidirektionale Kante. |
| Gerichtete Kante | Es handelt sich um eine unidirektionale Kante. |
| Beschwerter Rand | Ein Vorteil mit Mehrwert. |
| Grad | In Graph wird die Anzahl der mit einem Scheitelpunkt verbundenen Kanten 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 | Eckpunkte heißen benachbart, wenn eine Kante verbunden ist. |
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
Anwendungen der Graphdatenstruktur
Ein Graph hat viele Anwendungsfälle. Es gibt viele Algorithmen, die häufig Graphen verwenden. Hier sind einige der Anwendungen des Graphen:
- Google Maps verwendet Diagramme, um die Kreuzung zweier Straßen zu finden und die Entfernung zwischen zwei Orten zu berechnen.
Zum Beispiel, Dijkstra, um die kürzeste Entfernung zwischen Quell- und Zielort zu finden. - Facebook nutzt Graphen, um den gemeinsamen Freund der Nutzer zu finden. Sein Algorithmus betrachtet jeden Benutzer als Knoten eines Diagramms.
- Für die Ressourcenzuteilung wird DAG (Direct Asymmetric Graph) verwendet. Es prüft die Abhängigkeit der Ressourcen.
- Die Google-Suchmaschine verwendet Grafiken, um das Ranking für Websites zu erstellen.
- Ein Kartengerät verwendet die Diagrammdatenstruktur.
- Router und das Protokoll von t verwendet den Graphen, um den Pfad des Zielpfads zu lernen.
