Arten von Diagrammen in der Datenstruktur mit Beispielen

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

Es gibt verschiedene Arten von Graphen, je nach Position der Knoten und Kanten. Hier sind einige wichtige Graphtypen:

Gerichteter Graph

Die Kanten eines gerichteten Graphen enthalten Pfeile, die die Richtung angeben. Der Pfeil bestimmt, wohin die Kante zeigt oder wohin sie endet. Hier ist ein Beispiel für einen gerichteten Graphen.

Gerichteter Graph

• Wir können von Knoten A nach D gehen.
• Wir können jedoch nicht von Knoten D zu Knoten A gelangen, da die Kante von A nach D zeigt.
• Da der Graph keine Gewichtungen hat, kostet die Fahrt von Scheitelpunkt A nach D genauso viel wie die Fahrt von D nach F.

Ungerichteter Graph

Ein ungerichteter Graph enthält Kanten ohne Zeiger. Das bedeutet, dass man zwischen zwei Knoten in beide Richtungen reisen kann. Hier ist ein einfaches Beispiel für einen ungerichteten Graphen.

Ungerichteter Graph

In der obigen Grafik:

• Wir können von A nach B gelangen.
• Wir können auch von B nach A wechseln.
• Kanten enthalten keine Richtungen.

Es handelt sich um ein Beispiel für einen ungerichteten Graphen mit einer endlichen Anzahl von Knoten und Kanten ohne Gewichte.

Gewichtetes Diagramm

Ein Graph, dessen Kanten Gewichte oder Kosten aufweisen, wird als gewichteter Graph bezeichnet. Der numerische Wert repräsentiert im Allgemeinen die Kosten für die Bewegung von einem Knoten zu einem anderen. Sowohl gerichtete als auch ungerichtete Graphen können Kantengewichte haben. Hier ist ein Beispiel für einen gewichteten Graphen (gerichtet).

Gerichteter Graph mit Gewicht

• Von A nach B gibt es einen Vorteil, und das Gewicht beträgt 5, was bedeutet, dass der Übergang von A nach B uns 5 kostet.
• A zeigt auf B, aber in diesem Graphen hat B keine direkte Kante über A. Daher können wir nicht von B nach A reisen.
• Um von A nach F zu gelangen, gibt es mehrere Wege. Diese Wege sind ADF und ABF. Der Weg ADF kostet (10+11) oder 21.
• Hier kostet der Pfad ABF (5+15) oder 20. Hierbei addieren wir das Gewicht jeder Kante im Pfad.

Hier ist ein Beispiel für einen ungerichteten Graphen mit Gewichten:

Ungerichteter Graph mit Gewicht

Hier hat die Kante Gewicht, aber keine Richtung. Das bedeutet also, dass die Fahrt von Scheitelpunkt A nach D 10 kostet und umgekehrt.

Bidirektionaler Graph

Bidirektionale und ungerichtete Graphen haben eine gemeinsame Eigenschaft. Und zwar:

• Im Allgemeinen kann ein ungerichteter Graph eine Kante zwischen zwei Knoten aufweisen.

Beispielsweise:

• Hier kostet der Umzug von A nach D oder von D nach A 10.
• In einem bidirektionalen Graphen können wir zwei Kanten zwischen zwei Eckpunkten haben.

Ein Beispiel:

Bidirektionaler Graph

Die Reise von A nach D kostet uns 17, die Reise von D nach A hingegen 12. Daher können wir in einem ungerichteten Graphen nicht zwei unterschiedliche Gewichte zuweisen.

Unendliche Grafik

Der Graph enthält unendlich viele Kanten und Knoten. Ist ein Graph unendlich und gleichzeitig zusammenhängend, so besitzt er ebenfalls unendlich viele Kanten. Die erweiterten Kanten bedeuten, dass weitere Kanten mit diesen Knoten verbunden sein können. Hier ist ein Beispiel für einen unendlichen Graphen:

Unendliche Grafik

Nulldiagramm

Ein Nullgraph enthält nur Knoten, aber keine Kanten. Gegeben sei ein Graph G = (V, E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist. Er ist genau dann ein Nullgraph, wenn die Anzahl der Kanten E null ist. Hier ist ein Beispiel für einen Nullgraphen:

Nulldiagramm

Trivialer Graph

Eine Graphdatenstruktur gilt als trivial, wenn sie nur einen Knoten ohne Kanten enthält. Hier ist ein Beispiel für einen trivialen Graphen:

Multi-Graph

Ein Graph wird als Multigraph bezeichnet, wenn zwischen zwei Knoten mehrere Kanten existieren oder ein Knoten eine Schleife enthält. Der Begriff „Schleife“ in der Graphendatenstruktur bezeichnet eine Kante, die auf denselben Knoten verweist. Ein Multigraph kann gerichtet oder ungerichtet sein. Hier ist ein Beispiel für einen Multigraph:

Es gibt zwei Kanten von B nach A. Außerdem enthält Knoten E eine Schleife. Der obige Graph ist ein gerichteter Graph ohne Kantengewichte.

Vollständige Grafik

Ein Graph heißt vollständig, wenn jeder Knoten mit allen anderen Knoten durch gerichtete oder ungerichtete Kanten verbunden ist. Angenommen, es gibt insgesamt V Knoten und jeder Knoten hat genau V-1 Kanten. Dann wird dieser Graph als vollständiger Graph bezeichnet. In einem solchen Graphen ist jeder Knoten mit allen anderen Knoten durch Kanten verbunden. Hier ist ein Beispiel für einen vollständigen Graphen mit fünf Knoten:

Auf dem Bild ist zu erkennen, dass die Gesamtzahl der Knoten fünf beträgt und jeder Knoten genau vier Kanten hat.

Verbundenes Diagramm

Ein Graph heißt zusammenhängend, wenn man von einem Knoten aus zu jedem anderen Knoten gelangen kann. Dazu muss zwischen jedem Knotenpaar mindestens eine Kante existieren. Hier ist ein Beispiel für einen zusammenhängenden Graphen:

Hier folgt eine Erläuterung des oben dargestellten verbundenen Graphen:

• Angenommen, es gibt keine Kante zwischen C und F, dann können wir nicht von A nach G gelangen. Die Kante C nach F ermöglicht es uns jedoch, von einem gegebenen Knoten zu jedem beliebigen Knoten zu gelangen.
• Ein vollständiger Graph ist ein verbundener Graph, da wir von einem Knoten zu jedem anderen Knoten im gegebenen Graphen wechseln können.

Zyklischer Graph

Ein Graph wird als zyklisch bezeichnet, wenn er einen oder mehrere Zyklen enthält. Hier ist ein Beispiel für einen zyklischen Graphen:

Hier bilden die Knoten A, B und C einen Zyklus. Ein Graph kann mehrere Zyklen enthalten.

Gerichteter azyklischer Graph (DAG)

Ein Graph wird als gerichteter azyklischer Graph (DAG) bezeichnet, wenn er keine Zyklen enthält. DAGs sind wichtig bei der... Topologische Sortierung oder um die Ausführungsreihenfolge zu ermitteln. DAGs sind auch wichtig für die Erstellung von Scheduling-Systemen oder die Analyse von Ressourcenabhängigkeiten usw. Der obige Graph enthält jedoch keinen Zyklus. Hier ist ein einfaches Beispiel für einen gerichteten azyklischen Graphen (DAG):

Zyklusdiagramm

Ein Zyklusgraph ist nicht dasselbe wie ein zyklischer Graph. In einem Zyklusgraphen ist jeder Knoten mit genau zwei Kanten verbunden, was bedeutet, dass jeder Knoten genau zwei Grade hat. Hier ist ein Beispiel für einen Zyklusgraphen:

Zweiteiliger Graph

Diese Arten von Graphs Bipartite Graphen sind spezielle Graphen, bei denen die Knoten zwei Mengen zugeordnet sind. Ein bipartiter Graph muss folgender Regel genügen:

• Die beiden Mengen von Knotenpunkten sollten verschieden sein, das heißt, alle Knotenpunkte müssen in zwei Gruppen oder Mengen aufgeteilt werden.
• Gleichartige Knoten sollten keine Kanten bilden.

Euler-Diagramm

Eine Graph-Datenstruktur wird als Euler-Graph bezeichnet, wenn alle Knoten einen geraden Grad aufweisen. Der Grad eines Knotens bezeichnet die Anzahl der Kanten, die zu einem bestimmten Knoten führen oder von diesem ausgehen. Hier ist ein Beispiel für einen Euler-Graphen:

Alle Knoten haben einen geraden Grad. Die Knoten A, D, E und H haben den Grad zwei. Knoten C hat den Grad vier, was ebenfalls gerade ist.

Hamilton-Diagramm

Ein Hamilton-Graph ist ein zusammenhängender Graph, bei dem man von einem gegebenen Knoten aus alle Knoten besuchen kann, ohne denselben Knoten erneut zu besuchen oder dieselbe Kante zu benutzen. Diese Art von zusammenhängendem Graph wird als „Hamilton-Graph“ bezeichnet. Der Pfad, den man durchläuft, um zu überprüfen, ob der gegebene Graph ein Hamilton-Graph ist oder nicht, wird als Hamiltonpfad bezeichnet. Hier ist ein einfaches Beispiel für einen Hamilton-Graphen:

In diesem Bild können wir alle Eckpunkte von jedem Knoten im obigen Diagramm aus besuchen. Einer der Wege kann sein ADCHBEEs ist auch möglich, einen Hamiltonkreis zu finden. Ein Hamiltonkreis beginnt und endet im selben Knoten. Der Hamiltonkreis lautet also: ADCHBEA.

Häufig gestellte Fragen