Arten von Diagrammen in Datenstruktur und Anwendungen

Einführung

Ein Graph ist eine nichtlineare Struktur aus Knoten und Kanten. Es kann eine endliche oder unendliche Menge von Knoten enthalten, die von einer Kante gehalten werden, die ein Paar von Knoten verbindet. Datenstrukturen sind ein wesentlicher Bestandteil jedes Codierungskonzepts; Daher kann Ihnen ein solides Verständnis verschiedener Arten von Diagrammen in Datenstrukturen bei komplexen Problemen der realen Welt helfen.

In der heutigen Welt sind Daten Macht. Daher ist die effiziente Organisation von Daten für einen einfachen Zugriff für jeden Programmierer unerlässlich. Die Kenntnis von Datenstrukturen und ihrer Vielzahl von Diagrammen befähigt Ihre Programmierfähigkeiten, reale Probleme anzugehen und ihre Lösungen effektiv bereitzustellen.

Lernen Sie Data Science, um sich einen Vorteil gegenüber Ihren Mitbewerbern zu verschaffen

Werfen wir einen Blick auf verschiedene Arten von Diagrammen, die häufig in Datenstrukturen verwendet werden, und wie sie im wirklichen Leben angewendet werden.

Typen von Graphen in Datenstrukturen

Eine Datenstruktur ist ein praktischer Datenspeicherstandard für alle Sprachen, wie z. B. die Python-Graph-Datenstruktur oder die Java-Graph-Datenstruktur. Die Beherrschung aller Arten von Graphen sollte eine Priorität für jeden sein, der danach strebt, Datenstrukturen zu studieren. Da die Graphentheorie viele reale Anwendungen hat, werden sie in Datenstrukturen von entscheidender Bedeutung.

Die verschiedenen Arten von Diagrammen in Datenstrukturen können unten aufgelistet werden:

1. Nullgraph

Wie der Name schon sagt, ist der Nullgraph leer; mit anderen Worten, es ist ein Graph ohne Kanten. Es besteht nur aus isolierten Scheitelpunkten im Graphen mit einer leeren Kantenmenge.

2. Endlicher Graph

Wenn die Anzahl der Kanten und Knoten in einem Graphen aus einer endlichen Zahl besteht, dann wird der Graph als endlicher Graph bezeichnet.

3. Unendlicher Graph

Wenn man der Anzahl der Knoten und der Anzahl der Kanten in einem Graphen keine endliche Zahl zuordnen kann, wird der Graph als unendlicher Graph bezeichnet. Unendliche Graphen sind nicht zählbar, was bedeutet, dass Sie die Anzahl der Knoten oder Kanten in dieser Art von Graphen nicht zählen können.

4. Einfache Grafik

Ein Graph heißt einfach, wenn es zwischen zwei Knoten nur eine Kante gibt. So werden zwei Knoten in einem Graphen durch eine Kante verbunden, die eine eindeutige Beziehung zwischen ihnen identifizieren kann.

5. Multi-Grafik

Wenn in einem Graphen ein Knotenpaar mit mehreren Kanten verbunden ist, wird der Graph als Multigraph bezeichnet. Ein Multigraph besteht nicht aus Selbstschleifen. Es gibt zwei Arten von Kanten, die in einem Multigraphen existieren können. Sie sind:

• Parallele Kanten

Parallel verlaufende Kanten, wie zwei parallele Straßen, die von einer Quelle zum selben Ziel führen, werden als parallele Kanten bezeichnet.

• Schleife

Dies ist eine Kante, deren Quell- und Zielscheitel gleich sind.

Sehen Sie sich unsere US - Data Science-Programme an

6. Gerichteter Graph

Ein Graph heißt gerichtet, wenn alle zwischen zwei Knoten oder Scheitelpunkten vorhandenen Kanten eine definierte Richtung haben. Ein gerichteter Graph wird auch als Digraph bezeichnet. Wir können den Start- und Endknoten bestimmen, indem wir uns einen gerichteten Graphen ansehen. Denken Sie daran, dass alle Kanten in einem gerichteten Graphen gerichtet sein müssen, um als gerichteter Graph bezeichnet zu werden.

7. Ungerichteter Graph

Ein Graph wird als ungerichteter Graph bezeichnet, wenn es schwierig ist, den Anfangs- und Endknoten anhand seiner Kanten zu identifizieren. Genau wie bei einem gerichteten Graphen müssen die Kanten ungerichtet sein, damit er als ungerichteter Graph bezeichnet werden kann.

8. Verbundener Graph

Ein verbundener Graph ist ein Graph, bei dem zwischen allen Knoten mindestens ein Pfad existiert. Einfacher ausgedrückt: Wenn Sie von einem Knoten in einem verbundenen Diagramm ausgehen, sollten Sie in der Lage sein, jeden im Diagramm vorhandenen Knoten zu besuchen. Daher sollte es mindestens einen Pfad für jeden Knoten geben.

9. Getrennter Graph

Bei dieser Art von Graphen existiert keine Kante zwischen einem Knoten- oder Scheitelpunktpaar. Anders als bei verbundenen Graphen ist es daher nicht möglich, alle Knoten von irgendeiner Ecke aus zu erreichen. Wenn zwischen zwei Scheitelpunkten kein Pfad liegt, spricht man von einem unzusammenhängenden Graphen.

10. Vollständiges Diagramm

Ein Graph gilt nur dann als vollständig, wenn zwischen jedem Knoten eine Kante existiert, was bedeutet, dass eine Kante alle Knoten im Graphen verbindet. Ein vollständiger Graph mit n Knoten wird als Kn bezeichnet , und die Anzahl der Kanten im Graphen ist nC2 .

11. Zyklischer Graph

Ein Graph sollte mindestens eine zyklische Komponente haben, um als zyklischer Graph betrachtet zu werden. Wenn der Graph dagegen keinen Zyklus enthält, wird er als azyklischer Graph betrachtet.

12. Regelmäßige Grafik

In einem regulären Graphen sollten alle Ecken den gleichen Grad haben. Der Grad eines Knotens kann als die Anzahl der mit ihm verbundenen Knoten definiert werden. Daher sollten in einem regulären Graphen alle Knoten mit der gleichen Anzahl von Knoten verbunden sein.

13. Zweigeteilter Graph

Damit ein Graph bipartit ist, sollte er die folgenden Kriterien erfüllen.

• Der Graph sollte in Knotenmengen unterteilt werden.
• Kanten sollten sich nur zwischen einer Gruppe von Knoten zur anderen Seite bilden. Diese Regel verhindert die Verbindung zwischen zwei Scheitelpunkten derselben Knotenmenge.
• Die beiden Gruppen sollten keine gemeinsamen Eckpunkte zwischen sich haben.

Ein Graph, der alle obigen Regeln befolgt, sollte als zweigeteilter Graph betrachtet werden.

14. Beschriftetes Diagramm

Die Kanten in Graphen können gewichtet werden. Ein Gewicht, das einer Kante zugeordnet ist, kann als die Kosten für das Durchlaufen dieser Kante verstanden werden. Diese Werte können auf einem festen Parameter basieren und sich zwischen Diagrammen ändern. Wenn nun alle Kanten ein gewisses Gewicht haben, kann dieser Graph als beschrifteter Graph bezeichnet werden.

15. Gerichteter azyklischer Graph

Ein gerichteter azyklischer Graph ist eine Kombination aus gerichteten und azyklischen Graphen, bei denen die gerichteten Kanten des Graphen keine Form eines Zyklus bilden. Im Gegensatz dazu ist ein gerichteter zyklischer Graph ein Graph mit gerichteten Kanten, der einen Zyklus bildet.

Anwendung des Graphen in der Datenstruktur

Die prominenteste Anwendung eines Graphen in der Informatik ist die Darstellung des Rechenflusses. Einige andere bekannte Anwendungsfälle von Graphen sind:

1. Google Maps

In Google Maps definieren und berechnen grafische Datenstrukturen das Verkehrssystem. Wenn eine Straße auf eine andere Straße trifft und eine Kreuzung bildet, wird sie als Knoten betrachtet, und die Straße zwischen zwei solchen Knoten wird als Kante behandelt. Daher findet Google Maps anhand der grafischen Datenstruktur den kürzesten und schnellsten Weg zu Ihrem Ziel.

2. Facebook

Facebook verwendet ungerichtete Graphen, um einen Benutzer und die Freunde des Benutzers zu identifizieren. Jeder Benutzer wird als Scheitelpunkt behandelt, und die Verbindungen, die sich ihnen als Freunde anschließen, sind die Ränder des Netzwerks. Mit Algorithmen, die auf der Datenstruktur von Diagrammen basieren, schlägt Facebook „Menschen, die Sie vielleicht kennen“ vor und zeigt „gemeinsame Freunde“ an.

3. World Wide Web

Das World Wide Web ist ein Beispiel für einen gerichteten Graphen. Es ist auch die Grundidee hinter dem Google-Ranking-System. Im World Wide Web-System wird jede Website und Webanwendung als Knoten oder Vertices behandelt, und die Links von einer Website zur anderen werden als Edge betrachtet.

4. Betriebssystem

Das Betriebssystem ist ein häufig verwendeter Fall von Ressourcenzuordnungsdiagrammen, das jeden Prozess und jede Ressource als Knoten oder Scheitelpunkte verwendet. Kanten treten zwischen Ressourcen zum zugewiesenen Prozess oder vom anfordernden Prozess zu angeforderten Ressourcen auf. Manchmal kann dieser Zyklus eine Endlosschleife bilden und den Deadlock initialisieren.

5. Kartierungssystem

Ihr GPS ist ein häufig verwendeter Fall von Diagrammen, um nahe gelegene Restaurants, Geschäfte und Orte zu lokalisieren, die Sie mit Hilfe dieser Technologie suchen.

6. Microsoft-Excel

Directed Acyclic Graphs oder DAG wird in Microsoft Excel verwendet.

7. Der Dijkstra-Algorithmus

Der Dijkstra-Algorithmus verwendet eine Graphdatenstruktur, um den kürzesten Pfad zwischen zwei oder in einigen Fällen mehr als zwei Knoten zu identifizieren.

8. Flugnetze:

Die Berechnung optimierter Flugnetze ist eine weitere reale Anwendung der Graphdatenstruktur. Wenn Sie die Flughäfen als Knoten und die Strecken als Kanten betrachten, passen die Daten perfekt zu den Kriterien von Diagrammen. Deshalb werden mit Hilfe verschiedener erweiterter Algorithmen die besten Routen zwischen zwei Flughäfen oder Knoten ermittelt.

Dies sind die verschiedenen Anwendungen von Graphen in der Datenstruktur , die weltweit in verschiedenen Anwendungen und Systemen verwendet werden, um ihr reibungsloses Funktionieren zu organisieren und aufrechtzuerhalten.

Beginnen Sie Ihre Reise als Data Scientist

Wenn Sie Data Scientist werden und mit den verschiedenen Diagrammen, die wir gelernt haben, taktvoll mit Daten umgehen möchten, sehen Sie sich ein umfangreiches Angebot an Data Science-Kursen auf upGrad an. Einer der beliebtesten Kurse ist der PG-IIITB-Kurs zu Data Science , ein hervorragender Einstiegskurs für angehende und angehende Data Scientists!

Das bietet der Kurs.

• 360-Grad-Karriereunterstützung durch Branchenexperten und Mentoren
• Praktische Erfahrung mit Industrieprojekten und detaillierten Fallstudien, um den regelmäßigen Fortschritt zu messen
• Networking mit Data-Science-Experten aus allen Branchen, weltweit

Sie können sich auch alle anderen upGrad-Kurse zu Data Science ansehen .