Hier erhalten Sie einen Überblick über die Struktur der Diagrammdaten ...

Dieser Blog richtet sich an Entwickler, die den Kern eines Konzepts verstehen und nicht um den heißen Brei herumreden möchten. In diesem Beitrag werden wir die Struktur der Diagrammdaten verstehen. Fangen wir an.

Was sind Diagramme?

Grafiken sind nichtlineare Datenstrukturen mit zwei Komponenten, nämlich Kanten und Knoten.

Ein Knoten ist: -

1. eine Grundeinheit des Diagramms,
2. auch bekannt als Vertex oder Vertices und
3. kann beschriftet oder unbeschriftet sein.

Eine Kante ist:-

1. eine Verbindung zwischen zwei Knoten,
2. auch bekannt als Bögen und
3. kann beschriftet oder unbeschriftet sein.

Arten von Diagrammen: -

1. Nulldiagramm: Es hat keine Kanten,
2. Trival-Graph: Es hat nur einen Knoten,
3. Zyklisches Diagramm: Es enthält mindestens einen Zyklus,
4. Zyklusdiagramm: Alle Knoten sind verbunden, um einen Zyklus zu bilden,
5. Gerichteter Graph: Seine Kanten haben eine Richtung,
6. Ungerichteter Graph: Seine Kanten haben keine Richtung,
7. Gewichteter Graph: Jeder Kante wird ein Wert zugewiesen,
8. Verbundener Graph: Wir können jeden anderen Knoten von einem Knoten aus besuchen (es muss keine eindeutige Kante sein),
9. Unverbundenes Diagramm: Mindestens ein Knoten ist von einem Knoten getrennt,
10. Regulärer Graph: Jeder Knoten hat die gleiche Anzahl an Nachbarn,
11. Vollständiger Graph: Jeder Knoten ist durch eine eindeutige Kante mit einem anderen Knoten verbunden,
12. Gerichteter azyklischer Graph: Ein gerichteter Graph ohne Zyklen,
13. Zweiteiliger Graph: Seine Knoten können in zwei Mengen unterteilt werden, sodass zwischen den Mengen keine Kanten existieren.

Wie speichern wir Diagramme?

Es gibt 2 Möglichkeiten:

1. Angrenzende Matrix und
2. Angrenzende Matrix

Die benachbarte Matrix ist eine 2D-Matrix, die die Diagrammdatenstruktur darstellt. Die Zeilen und Spalten stellen Knoten dar und der Wert in der Matrix stellt die Kanten dar.

Im obigen Bild sind 4 Knoten durch die Kanten verbunden. Knoten A ist mit allen Knoten verbunden und daher wird der Wert als 1 in den Zellen addiert, in denen A (entweder Zeile oder Spalte) Zeilen oder Spalten anderer Knoten schneidet. Knoten B ist nur mit Knoten A verbunden, was zu einem Wert 1 in der Zelle führt, in der sich Knoten B mit Knoten A schneidet, und andere Zellen haben einen Wert 0.

Die Zeitkomplexität zum Hinzufügen oder Löschen einer Kante für die angrenzende Matrix beträgt O(1). Es kann verwendet werden, wenn: -

1. Der Graph hat die maximal möglichen Kanten,
2. Es gibt keine Speicherbeschränkung und
3. Das Diagramm hat eine komplexe Struktur.

Die benachbarte Liste speichert das Diagramm mithilfe mehrerer verknüpfter Listen oder Arrays. Die Zeilen stellen den Knoten dar (siehe Abbildung unten), und die in den Zeilen vorhandenen Werte stellen den Nachbarn dar.

Im obigen Bild gibt es 5 Knoten. Knoten A ist mit Knoten B und Knoten D verbunden, weshalb das erste Array diese Werte hat. In ähnlicher Weise ist Knoten B mit Knoten A, Knoten C, Knoten D und Knoten E verbunden, sodass das zweite Array diese Knoten im zweiten Array enthält.

Die Zeitkomplexität zum Abrufen oder Löschen einer Kante beträgt O(n) und die Zeitkomplexität zum Hinzufügen einer Kante beträgt O(1). Die nebenstehende Liste kann verwendet werden, wenn: -

1. Der Knoten hat weniger Kanten,
2. Es gibt Speicherbeschränkungen und
3. Das Diagramm ist weniger komplex.

Abb: Visueller Vergleich zwischen benachbarter Liste und benachbarter Matrix.

Anwendungsfälle für die Diagramme

Ein beliebtes Beispiel für die Struktur von Diagrammdaten ist: In einem Fußballfeld kann jeder Spieler als Knoten betrachtet werden und seine Interaktionen stellen Kanten dar.

Grafiken werden in ähnlichen Szenarien wie im vorherigen Beispiel verwendet, wie zum Beispiel: -

1. in sozialen Netzwerken, in denen jeder ein Knotenpunkt ist,
2. in Computernetzwerken, in denen PCs und Router die Knoten sind,
3. im Verkehrsnetz und so weiter...

Das obige ist der detaillierte Inhalt vonHier erhalten Sie einen Überblick über die Struktur der Diagrammdaten .... Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!