Arten von Diagrammen in der Datenstruktur mit Beispielen

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

Abhängig von der Position der Knoten und Kanten können Diagramme unterschiedlicher Art sein. Hier sind einige wichtige Arten von Diagrammen:

Gerichteter Graph

Die Kanten des gerichteten Diagramms enthalten Pfeile, die die Richtung angeben. Der Pfeil bestimmt, wohin die Kante zeigt oder endet.

Hier ist ein Beispiel für den gerichteten Graphen.

• Wir können von Knoten A nach D gehen.
• Wir können jedoch nicht von Knoten D zu Knoten A gehen, 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

Ungerichteter Graph enthält Kanten ohne Zeiger. Das bedeutet, dass wir zwischen zwei Scheitelpunkten umgekehrt reisen können.

Hier ist ein einfaches Beispiel für den ungerichteten Graphen.

In der obigen Grafik:

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

Es ist ein Beispiel für einen ungerichteten Graphen mit einer endlichen Anzahl von Eckpunkten und Kanten ohne Gewichte.

Gewichtetes Diagramm

Ein Diagramm, das an den Rändern Gewichte oder Kosten enthält, wird als gewichtetes Diagramm bezeichnet. Der numerische Wert stellt im Allgemeinen die Umzugskosten von einem Scheitelpunkt zu einem anderen Scheitelpunkt dar. Sowohl der gerichtete als auch der ungerichtete Graph können Gewichte an ihren Kanten haben.

Hier ist ein Beispiel für ein gewichtetes Diagramm (gerichtet).

• Von A nach B gibt es eine Kante und das Gewicht beträgt 5, was bedeutet, dass der Umzug von A nach B uns 5 kostet.
• A zeigt auf B, aber in diesem Diagramm hat B keine direkte Kante über A. Wir können also nicht von B nach A reisen.
• Wenn wir jedoch von A nach F gelangen wollen, gibt es mehrere Wege. Die Pfade sind ADF, ABF. Der ADF kostet (10+11) oder 21.
• Hier kostet der Pfad ABF (5+15) oder 20. Hier addieren wir das Gewicht jeder Kante im Pfad.

Hier ist ein Beispiel eines ungerichteten Diagramms mit Gewichtungen:

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. Das ist

• Im Allgemeinen kann der ungerichtete Graph eine Kante zwischen zwei Scheitelpunkten haben.

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.

Hier ist ein Beispiel:

Die Fahrt von A nach D kostet uns 17, die Fahrt von D nach A hingegen 12. Wir können also nicht zwei unterschiedliche Gewichte zuweisen, wenn es sich um einen ungerichteten Graphen handelt.

Unendliche Grafik

Der Graph enthält unendlich viele Kanten und Knoten. Wenn ein Graph unendlich ist und auch ein zusammenhängender Graph, dann enthält er auch unendlich viele Kanten. Die erweiterten Kanten bedeuten hier, dass mehr Kanten über Kanten mit diesen Knoten verbunden sein können.

Hier ist ein Beispiel für den unendlichen Graphen:

Nulldiagramm

Null Graph enthält nur Knoten oder Scheitelpunkte, aber keine Kanten. Wenn ein Graph G = (V, E) gegeben ist, in dem V Eckpunkte und E Kanten sind, ist er null, wenn die Anzahl der Kanten E Null ist.

Hier ist ein Beispiel für ein Nulldiagramm:

Trivialer Graph

Eine Diagrammdatenstruktur gilt als trivial, wenn nur ein Scheitelpunkt oder Knoten ohne Kanten vorhanden ist.

Hier ist ein Beispiel für einen trivialen Graphen:

Multi-Graph

Ein Graph wird Multigraph genannt, wenn mehrere Kanten zwischen zwei Scheitelpunkten vorhanden sind oder der Scheitelpunkt eine Schleife aufweist. Der Begriff „Schleife“ in der Graphdatenstruktur bezeichnet eine Kante, die auf denselben Knoten oder Scheitelpunkt zeigt. Multigraph kann gerichtet oder ungerichtet sein.

Hier ist ein Beispiel für ein Multi-Graph:

Es gibt zwei Kanten von B nach A. Darüber hinaus hat der Scheitelpunkt E eine Selbstschleife. Der obige Graph ist ein gerichteter Graph ohne Gewichte an den Kanten.

Vollständige Grafik

Ein Graph ist vollständig, wenn jeder Knoten mit allen anderen Knoten gerichtete oder ungerichtete Kanten hat.

Angenommen, es gibt insgesamt V Scheitelpunkte und jeder Scheitelpunkt hat genau V-1 Kanten. Dann wird dieses Diagramm als vollständiges Diagramm bezeichnet. Bei dieser Art von Diagramm ist jeder Scheitelpunkt über Kanten mit allen anderen Scheitelpunkten verbunden.

Hier ist ein Beispiel eines vollständigen Diagramms mit fünf Eckpunkten:

Im Bild sehen Sie, dass die Gesamtzahl der Knoten fünf beträgt und alle Knoten genau vier Kanten haben.

Verbundenes Diagramm

Ein Graph wird als verbundener Graph bezeichnet, wenn wir von einem Knoten oder Scheitelpunkt ausgehen und alle Knoten vom Startknoten aus durchlaufen. Dazu sollte zwischen jedem Knoten- oder Eckpunktpaar mindestens eine Kante vorhanden sein.

Hier ist ein Beispiel für ein verbundenes Diagramm:

Hier ist eine Erklärung des obigen Diagramms „vollständiges Diagrammbeispiel“:

• Vorausgesetzt, es gibt keine Kante zwischen C und F, können wir nicht von A nach G reisen. Die Kante C nach F ermöglicht es uns jedoch, von einem bestimmten Knoten zu jedem Knoten zu reisen.
• 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 Diagramm wird als zyklisch bezeichnet, wenn im Diagramm ein oder mehrere Zyklen vorhanden sind.

Hier ist ein Beispiel für einen zyklischen Graphen:

Hier bilden die Scheitelpunkte A, B und C einen Kreis.

Ein Diagramm kann mehrere Zyklen enthalten.

Gerichteter azyklischer Graph (DAG)

Ein Graph wird als gerichteter azyklischer Graph oder DAG bezeichnet, wenn sich in einem Graphen keine Zyklen befinden. DAG ist dabei wichtig Topologische Sortierung oder den Ausführungsauftrag finden. DAG ist auch wichtig für die Erstellung von Planungssystemen oder das Scannen von Ressourcenabhängigkeiten usw. Die obige Grafik enthält jedoch keinen Zyklus.

Hier ist ein einfaches Beispiel für einen gerichteten azyklischen Graphen (DAG):

Zyklusdiagramm

Das Zyklusdiagramm ist nicht dasselbe wie das zyklische Diagramm. Im Zyklusdiagramm hat jeder Knoten genau zwei verbundene Kanten, was bedeutet, dass jeder Knoten genau zwei Grad hat.

Hier ist ein Beispiel für ein Zyklusdiagramm:

Zweiteiliger Graph

Diese Arten von Graphs sind spezielle Arten von Diagrammen, bei denen Scheitelpunkte zwei Mengen zugeordnet sind.

Der zweiteilige Graph muss der Regel folgen:

• Zwei Sätze von Scheitelpunkten sollten unterschiedlich sein, was bedeutet, dass alle Scheitelpunkte in zwei Gruppen oder Sätze unterteilt werden müssen.
• Gleiche Scheitelpunkte sollten keine Kanten bilden.

Euler-Diagramm

Diagrammdatenstrukturen gelten als Euler-Diagramm, wenn alle Scheitelpunkte einen geraden Grad haben. Der Begriff Scheitelpunktgrad bezeichnet die Anzahl der Kanten, die auf einen bestimmten Scheitelpunkt zeigen oder von diesem ausgehen.

Hier ist ein Beispiel für ein Euler-Diagramm:

Alle Eckpunkte haben gerade Grade. Die Scheitelpunkte A, D, E und H haben zwei Grade. Hier hat Knoten C vier Grad, was gerade ist.

Hamilton-Diagramm

Der Hamilton-Graph ist ein Verbindungsgraph, bei dem Sie alle Scheitelpunkte eines bestimmten Scheitelpunkts besuchen können, ohne denselben Knoten erneut aufzurufen oder dieselbe Kante zu verwenden. Diese Art von verbundenem Diagramm ist als „Hamilton-Diagramm“ bekannt. Der Pfad, den Sie besuchen, um zu überprüfen, ob der gegebene Graph ein Hamilton-Graph ist oder nicht, wird als Hamilton-Pfad bezeichnet.

Hier ist ein einfaches Diagrammbeispiel eines Hamilton:

In diesem Bild können wir alle Eckpunkte von jedem Knoten im obigen Diagramm aus besuchen. Einer der Wege kann sein ADCHBE. Es ist auch möglich, einen Hamilton-Zyklus zu finden. Der Hamilton-Zyklus beginnt und endet am selben Scheitelpunkt. So wird der Hamilton-Zyklus sein ADCHBEA.