Einführung in Graph in Data Structure
Graphen sind nichtlineare Datenstrukturen mit einer endlichen Menge von Knoten und Kanten. Die Knoten sind die Elemente und Kanten sind geordnete Verbindungspaare zwischen den Knoten.
Beachten Sie das Wort nicht linear. Eine nichtlineare Datenstruktur ist eine solche, bei der die Elemente nicht in sequentieller Reihenfolge angeordnet sind. Beispielsweise ist ein Array eine lineare Datenstruktur, da die Elemente nacheinander angeordnet sind. Sie können alle Elemente eines Arrays in einem Durchlauf durchlaufen. Dies ist bei nichtlinearen Datenstrukturen nicht der Fall. Die Elemente einer nichtlinearen Datenstruktur sind in mehreren Ebenen angeordnet und folgen häufig einem hierarchischen Muster. Diagramme sind nicht linear.
Das nächste Wort, auf das man achten muss, ist endlich. Wir definieren den Graphen so, dass er eine endliche und abzählbare Anzahl von Knoten hat. Dies ist ein eher unangenehmer Begriff. Grundsätzlich kann ein Graph unendlich viele Knoten haben und dennoch endlich sein. Zum Beispiel ein Stammbaum, der bis zu Adam und Eva zurückreicht. Dies ist ein relativ unendlicher Graph, der aber immer noch zählbar ist und daher als endlich angesehen wird.
Beispiel aus der Praxis
Das beste Beispiel für Grafiken in der realen Welt ist Facebook. Jede Person auf Facebook ist ein Knoten und durch Kanten verbunden. A ist ein Freund von B. B ist ein Freund von C und so weiter.
Terminologien
Hier sind die Terminologien des Graphen in der Datenstruktur aufgeführt
1. Graphendarstellung: Im Allgemeinen wird ein Graph als ein Paar von Mengen (V, E) dargestellt. V ist die Menge der Eckpunkte oder Knoten. E ist die Menge der Kanten. Im obigen Beispiel
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Knoten oder Scheitelpunkt: Die Elemente eines Diagramms sind durch Kanten verbunden.
3. Kanten: Ein Pfad oder eine Linie zwischen zwei Eckpunkten in einem Diagramm.
4. Benachbarte Knoten: Zwei Knoten werden als benachbart bezeichnet, wenn sie über eine Kante verbunden sind. Im obigen Beispiel grenzt der Knoten A an die Knoten B, C und D, nicht jedoch an den Knoten E.
5. Pfad: Pfad ist eine Folge von Kanten zwischen zwei Knoten. Es ist im Wesentlichen eine Überquerung, die an einem Knoten beginnt und an einem anderen endet. Im obigen Beispiel gibt es mehrere Pfade von Knoten A zu Knoten E.
Pfad (A, E) = (AB, BE)
ODER
Pfad (A, E) = (AC, CD, DE)
ODER
Pfad (A, E) = (AD, DE)
6. Ungerichtetes Diagramm: Bei einem ungerichteten Diagramm geben die Kanten keine bestimmte Richtung an. Die Kanten sind bidirektional.
Beispiel
Somit kann in diesem Beispiel die Kante AC sowohl von A nach C als auch von C nach A durchlaufen werden. Ähnlich wie bei allen Kanten. Ein Pfad von Knoten B zu Knoten C wäre entweder (BA, AC) oder (BD, DC).
7. Gerichteter Graph: Ein gerichteter Graph ist ein Graph, bei dem die Kanten nur in einer bestimmten Richtung durchlaufen werden können.
Beispiel
Im selben Beispiel sind die Kanten jetzt also gerichtet. Sie können die Kante nur entlang ihrer Richtung überqueren. Es gibt jetzt keinen Pfad von Knoten B zu Knoten C.
8. Gewichteter Graph: Ein gewichteter Graph ist einer, bei dem die Kanten einem Gewicht zugeordnet sind. Dies sind im Allgemeinen die Kosten für das Überqueren der Kante.
Beispiel
Im selben Beispiel haben die Kanten nun ein bestimmtes Gewicht. Es gibt zwei mögliche Pfade zwischen Knoten A und Knoten E.
Pfad1 = (AB, BD, DE), Gewicht1 = 3 + 2 + 5 = 10
Pfad2 = (AC, CD, DE), Gewicht2 = 1 + 3 + 5 = 9
Natürlich würde man Path2 vorziehen, wenn das Ziel darin besteht, Knoten E von Knoten A mit minimalen Kosten zu erreichen.
Grundlegende Operationen auf Graph
Hier sind die Grundfunktionen des Graphen aufgeführt
1. Vertex hinzufügen / entfernen
Dies ist die einfachste Operation in der Grafik. Sie fügen einem Diagramm einfach einen Scheitelpunkt hinzu. Es muss nicht durch eine Kante mit einem anderen Scheitelpunkt verbunden sein. Wenn Sie einen Scheitelpunkt entfernen, müssen Sie alle Kanten entfernen, die vom gelöschten Scheitelpunkt ausgehen und an diesem enden.
2. Kante hinzufügen / entfernen
Diese Operation fügt eine Kante zwischen zwei Scheitelpunkten hinzu oder entfernt sie. Wenn alle Kanten, die von einem Scheitelpunkt ausgehen und an diesem enden, gelöscht werden, wird der Scheitelpunkt zu einem isolierten Scheitelpunkt.
3. Breitensuche (BFS)
Dies ist eine Traversierungsoperation in der Grafik. BFS durchläuft das Diagramm horizontal. Dies bedeutet, dass alle Knoten auf einer Ebene durchlaufen werden, bevor zur nächsten Ebene übergegangen wird.
Der BFS-Algorithmus beginnt am oberen Rand des ersten Knotens im Diagramm und durchläuft dann alle angrenzenden Knoten. Sobald alle benachbarten Knoten durchlaufen sind, wiederholt der Algorithmus das gleiche Verfahren für untergeordnete Knoten.
Beispiel
Das Durchlaufen des obigen Graphen in BFS-Weise würde zu A -> B -> C -> D -> E -> F -> G führen. Der Algorithmus startet am Knoten A und durchläuft alle seine benachbarten Knoten B, C und D. Er markiert alle vier Knoten wie besucht. Sobald alle benachbarten Knoten von A durchlaufen sind, bewegt sich der Algorithmus zum ersten benachbarten Knoten von A und wiederholt die gleiche Prozedur. In diesem Fall ist der Knoten B und die benachbarten Knoten zu B sind E und F. Als nächstes werden die benachbarten Knoten zu C durchlaufen. Sobald alle Knoten besucht sind, endet die Operation.
4. Tiefensuche (DFS)
Die Tiefensuche oder DFS durchläuft das Diagramm vertikal. Es beginnt mit dem Wurzelknoten oder dem ersten Knoten des Graphen und durchläuft alle untergeordneten Knoten, bevor es zu den benachbarten Knoten wechselt.
Beispiel
Das Durchlaufen des obigen Graphen in BFS-Weise würde zu A -> B -> E -> F -> C -> G -> D führen. Der Algorithmus startet bei Knoten A und durchläuft alle seine untergeordneten Knoten. Sobald es auf B stößt, scheint es weitere untergeordnete Knoten zu haben. Daher werden die Kindknoten von B durchlaufen, bevor zum nächsten Kindknoten von A übergegangen wird.
Realistische Implementierung von Diagrammen
- Entwurf von Stromkreisen für die Energieübertragung.
- Design des Netzwerks von miteinander verbundenen Computern.
- Untersuchung der molekularen, chemischen und zellulären Struktur einer Substanz, zB der menschlichen DNA.
- Gestaltung von Verkehrswegen zwischen Städten und Orten innerhalb einer Stadt.
Fazit - Grafik in Datenstruktur
Diagramme sind ein sehr nützliches Konzept in Datenstrukturen. Es hat praktische Implementierungen in fast allen Bereichen. Es ist sehr wichtig, die Grundlagen der Graphentheorie zu verstehen, um ein Verständnis für die Algorithmen der Graphstruktur zu entwickeln.
Dieser Artikel war lediglich eine Einführung in Grafiken. Es ist nur ein Sprungbrett. Es wird empfohlen, tiefer in das Thema Graphentheorie einzutauchen.
Empfohlene Artikel
Dies ist eine Anleitung zum Diagramm in der Datenstruktur. Hier diskutieren wir die Terminologien und grundlegenden Operationen von Graphen in der Datenstruktur. Sie können auch den folgenden Artikel lesen, um mehr zu erfahren -
- Fragen im Vorstellungsgespräch zur Datenstruktur
- Datenmodell in Cassandra
- Was ist Data Mart?
- Was ist ein Data Scientist?