graph implementation c using adjacency list
Dieses Tutorial erklärt die Implementierung von Diagrammen in C ++. Außerdem erfahren Sie mehr über verschiedene Arten, Darstellungen und Anwendungen von Diagrammen:
Ein Graph ist eine nichtlineare Datenstruktur. Ein Diagramm kann als eine Sammlung von Knoten definiert werden, die auch als 'Scheitelpunkte' und 'Kanten' bezeichnet werden und zwei oder mehr Scheitelpunkte verbinden.
Ein Graph kann auch als zyklischer Baum angesehen werden, in dem Eckpunkte keine Eltern-Kind-Beziehung haben, sondern eine komplexe Beziehung zwischen ihnen aufrechterhalten.
implizites Warten und explizites Warten in Selen
=> Klicken Sie hier für die Absolute C ++ - Schulungsserie.
Was du lernen wirst:
Was ist ein Graph in C ++?
Wie oben erwähnt, ist ein Graph in C ++ eine nichtlineare Datenstruktur, die als Sammlung von Eckpunkten und Kanten definiert ist.
Es folgt ein Beispiel für eine Diagrammdatenstruktur.
Oben ist ein Beispielgraph G angegeben. Graph G ist eine Menge von Eckpunkten {A, B, C, D, E} und eine Menge von Kanten {(A, B), (B, C), (A, D), (D, E), (E, C), (B, E), (B, D)}.
Arten von Graphen - gerichtete und ungerichtete Graphen
Ein Diagramm, in dem die Kanten keine Richtungen haben, wird als ungerichtetes Diagramm bezeichnet. Das oben gezeigte Diagramm ist ein ungerichtetes Diagramm.
Ein Diagramm, dem die Kanten Richtungen zugeordnet sind, wird als gerichtetes Diagramm bezeichnet.
Im Folgenden finden Sie ein Beispiel für einen gerichteten Graphen.
In dem oben gezeigten gerichteten Graphen bilden Kanten ein geordnetes Paar, wobei jede Kante einen bestimmten Pfad von einem Scheitelpunkt zu einem anderen Scheitelpunkt darstellt. Der Scheitelpunkt, von dem aus der Pfad initiiert wird, heißt „ Anfangsknoten 'Während der Scheitelpunkt, in den der Pfad endet, als' Terminalknoten ”.
Somit ist in der obigen Grafik die Menge der Eckpunkte {A, B, C, D, E} und die Menge der Kanten ist {(A, B), (A, D), (B, C), (B, E. ), (D, E) (E, C)}.
Wir werden die Graphenterminologie oder die allgemeinen Begriffe diskutieren, die in Bezug auf den Graph unten verwendet werden.
Graph Terminologie
- Scheitel: Jeder Knoten des Graphen wird als Scheitelpunkt bezeichnet. In der obigen Grafik sind A, B, C und D die Eckpunkte der Grafik.
- Kante: Die Verbindung oder der Pfad zwischen zwei Eckpunkten wird als Kante bezeichnet. Es verbindet zwei oder mehr Eckpunkte. Die verschiedenen Kanten im obigen Diagramm sind AB, BC, AD und DC.
- Benachbarter Knoten: Wenn in einem Diagramm zwei Knoten durch eine Kante verbunden sind, werden sie als benachbarte Knoten oder Nachbarn bezeichnet. In der obigen Grafik sind die Eckpunkte A und B durch die Kante AB verbunden. Somit sind A und B benachbarte Knoten.
- Grad des Knotens: Die Anzahl der Kanten, die mit einem bestimmten Knoten verbunden sind, wird als Grad des Knotens bezeichnet. In der obigen Grafik hat Knoten A einen Grad 2.
- Pfad: Die Folge von Knoten, denen wir folgen müssen, wenn wir in einem Diagramm von einem Scheitelpunkt zum anderen reisen müssen, wird als Pfad bezeichnet. Wenn wir in unserem Beispieldiagramm von Knoten A nach C gehen müssen, lautet der Pfad A-> B-> C.
- Geschlossener Weg: Wenn der Anfangsknoten mit einem Endknoten identisch ist, wird dieser Pfad als geschlossener Pfad bezeichnet.
- Einfacher Weg: Ein geschlossener Pfad, in dem alle anderen Knoten unterschiedlich sind, wird als einfacher Pfad bezeichnet.
- Zyklus: Ein Pfad, in dem es keine wiederholten Kanten oder Scheitelpunkte gibt und der erste und der letzte Scheitelpunkt gleich sind, wird als Zyklus bezeichnet. In der obigen Grafik ist A-> B-> C-> D-> A ein Zyklus.
- Verbundenes Diagramm: Ein verbundener Graph ist derjenige, in dem sich zwischen jedem der Eckpunkte ein Pfad befindet. Dies bedeutet, dass es keinen einzigen Scheitelpunkt gibt, der isoliert oder ohne Verbindungskante ist. Das oben gezeigte Diagramm ist ein zusammenhängendes Diagramm.
- Vollständige Grafik: Ein Diagramm, in dem jeder Knoten mit einem anderen verbunden ist, wird als vollständiges Diagramm bezeichnet. Wenn N die Gesamtzahl der Knoten in einem Diagramm ist, enthält das vollständige Diagramm N (N-1) / 2 Anzahl der Kanten.
- Gewichtete Grafik: Ein positiver Wert, der jeder Kante zugewiesen wird und deren Länge (Abstand zwischen den durch eine Kante verbundenen Scheitelpunkten) angibt, wird als Gewicht bezeichnet. Das Diagramm mit gewichteten Kanten wird als gewichtetes Diagramm bezeichnet. Das Gewicht einer Kante e wird mit w (e) bezeichnet und gibt die Kosten für das Durchqueren einer Kante an.
- Diagramm: Ein Digraph ist ein Graph, in dem jede Kante einer bestimmten Richtung zugeordnet ist und die Durchquerung nur in einer bestimmten Richtung erfolgen kann.
Diagrammdarstellung
Die Art und Weise, wie die Graphdatenstruktur im Speicher gespeichert wird, wird als 'Darstellung' bezeichnet. Das Diagramm kann als sequentielle Darstellung oder als verknüpfte Darstellung gespeichert werden.
Diese beiden Typen werden nachfolgend beschrieben.
Sequentielle Darstellung
In der sequentiellen Darstellung von Graphen verwenden wir die Adjazenzmatrix. Eine Adjazenzmatrix ist eine Matrix der Größe n x n, wobei n die Anzahl der Eckpunkte im Diagramm ist.
Die Zeilen und Spalten der Adjazenzmatrix repräsentieren die Eckpunkte in einem Diagramm. Das Matrixelement wird auf 1 gesetzt, wenn zwischen den Eckpunkten eine Kante vorhanden ist. Wenn die Kante nicht vorhanden ist, wird das Element auf 0 gesetzt.
Im Folgenden finden Sie ein Beispieldiagramm, das die Adjazenzmatrix zeigt.
Wir haben die Adjazenzmatrix für das obige Diagramm gesehen. Beachten Sie, dass dies ein ungerichteter Graph ist und wir sagen können, dass die Kante in beide Richtungen vorhanden ist. Zum Beispiel, Da die Kante AB vorhanden ist, können wir schließen, dass auch die Kante BA vorhanden ist.
In der Adjazenzmatrix können wir die Wechselwirkungen der Eckpunkte sehen, die Matrixelemente sind, die auf 1 gesetzt werden, wenn die Kante vorhanden ist, und auf 0, wenn die Kante fehlt.
Lassen Sie uns nun die Adjazenzmatrix eines gerichteten Graphen sehen.
Wie oben gezeigt, ist das Schnittelement in der Adjazenzmatrix genau dann 1, wenn eine Kante von einem Scheitelpunkt zum anderen gerichtet ist.
In der obigen Grafik haben wir zwei Kanten von Scheitelpunkt A. Eine Kante endet in Scheitelpunkt B, während die zweite in Scheitelpunkt C endet. Somit wird in der Adjazenzmatrix der Schnittpunkt von A & B als Schnittpunkt von A & C auf 1 gesetzt.
Als nächstes sehen wir die sequentielle Darstellung für den gewichteten Graphen.
Unten ist das gewichtete Diagramm und seine entsprechende Adjazenzmatrix angegeben.
Wir können sehen, dass sich die sequentielle Darstellung eines gewichteten Graphen von den anderen Arten von Graphen unterscheidet. Hier werden die Nicht-Null-Werte in der Adjazenzmatrix durch das tatsächliche Gewicht der Kante ersetzt.
Die Kante AB hat das Gewicht = 4, daher setzen wir in der Adjazenzmatrix den Schnittpunkt von A und B auf 4. In ähnlicher Weise werden alle anderen Nicht-Null-Werte auf ihre jeweiligen Gewichte geändert.
Die Adjazenzliste ist einfacher zu implementieren und zu befolgen. Das Durchlaufen, d. H. Um zu überprüfen, ob es eine Kante von einem Scheitelpunkt zum anderen gibt, benötigt O (1) Zeit, und das Entfernen einer Kante benötigt auch O (1).
Unabhängig davon, ob das Diagramm dünn (weniger Kanten) oder dicht ist, nimmt es immer mehr Platz ein.
Verknüpfte Darstellung
Wir verwenden die Adjazenzliste für die verknüpfte Darstellung des Diagramms. Die Darstellung der Adjazenzliste verwaltet jeden Knoten des Diagramms und eine Verknüpfung zu den Knoten, die an diesen Knoten angrenzen. Wenn wir alle benachbarten Knoten durchlaufen, setzen wir den nächsten Zeiger am Ende der Liste auf null.
Betrachten wir zunächst einen ungerichteten Graphen und seine Adjazenzliste.
Wie oben gezeigt, haben wir für jeden Knoten eine verknüpfte Liste (Adjazenzliste). Vom Scheitelpunkt A haben wir Kanten zu den Scheitelpunkten B, C und D. Somit sind diese Knoten in der entsprechenden Adjazenzliste mit dem Knoten A verknüpft.
Als nächstes erstellen wir eine Adjazenzliste für den gerichteten Graphen.
In dem oben gerichteten Diagramm sehen wir, dass es keine Kanten gibt, die vom Scheitelpunkt E stammen. Daher ist die Adjazenzliste für den Scheitelpunkt E leer.
wie man effektive Testfälle schreibt
Lassen Sie uns nun die Adjazenzliste für das gewichtete Diagramm erstellen.
Für ein gewichtetes Diagramm fügen wir im Adjazenzlistenknoten ein zusätzliches Feld hinzu, um das Gewicht der Kante wie oben gezeigt anzugeben.
Das Hinzufügen eines Scheitelpunkts zur Adjazenzliste ist einfacher. Durch die Implementierung der verknüpften Liste wird außerdem Platz gespart. Wenn wir herausfinden müssen, ob es eine Kante zwischen einem Scheitelpunkt und einem anderen gibt, ist die Operation nicht effizient.
Grundlegende Operationen für Diagramme
Im Folgenden sind die grundlegenden Operationen aufgeführt, die wir für die Diagrammdatenstruktur ausführen können:
- Fügen Sie einen Scheitelpunkt hinzu: Fügt dem Diagramm einen Scheitelpunkt hinzu.
- Fügen Sie eine Kante hinzu: Fügt eine Kante zwischen den beiden Scheitelpunkten eines Diagramms hinzu.
- Zeigen Sie die Scheitelpunkte des Diagramms an: Zeigen Sie die Eckpunkte eines Diagramms an.
Implementierung von C ++ - Diagrammen mithilfe der Adjazenzliste
Jetzt präsentieren wir eine C ++ - Implementierung, um anhand der Adjazenzliste ein einfaches Diagramm zu demonstrieren.
Hier zeigen wir die Adjazenzliste für einen gewichteten gerichteten Graphen an. Wir haben zwei Strukturen verwendet, um die Adjazenzliste und die Kanten des Diagramms zu halten. Die Adjazenzliste wird angezeigt als (start_vertex, end_vertex, weight).
Das C ++ - Programm lautet wie folgt:
#include using namespace std; // stores adjacency list items struct adjNode { int val, cost; adjNode* next; }; // structure to store edges struct graphEdge { int start_ver, end_ver, weight; }; class DiaGraph{ // insert new nodes into adjacency list from given graph adjNode* getAdjListNode(int value, int weight, adjNode* head) { adjNode* newNode = new adjNode; newNode->val = value; newNode->cost = weight; newNode->next = head; // point new node to current head return newNode; } int N; // number of nodes in the graph public: adjNode **head; //adjacency list as array of pointers // Constructor DiaGraph(graphEdge edges(), int n, int N) { // allocate new node head = new adjNode*(N)(); this->N = N; // initialize head pointer for all vertices for (int i = 0; i Ausgabe:
Ausgabe:
Diagramm Adjazenzliste
(start_vertex, end_vertex, weight):
(0, 2, 4) (0, 1, 2)
(1, 4, 3)
(2, 3, 2)
(3, 1, 4)
(4, 3, 3)
Anwendungen von Graphen
Lassen Sie uns einige Anwendungen von Graphen diskutieren.
- Diagramme werden in der Informatik häufig verwendet, um Netzwerkdiagramme oder semantische Diagramme oder sogar den Berechnungsfluss darzustellen.
- In Compilern werden häufig Diagramme verwendet, um die Zuordnung von Ressourcen zu Prozessen oder die Datenflussanalyse usw. darzustellen.
- Diagramme werden in einigen spezialisierten Compilern auch zur Abfrageoptimierung in Datenbanksprachen verwendet.
- In Social-Networking-Sites sind Diagramme die Hauptstrukturen zur Darstellung des Netzwerks von Personen.
- Grafiken werden häufig verwendet, um das Transportsystem, insbesondere das Straßennetz, aufzubauen. Ein beliebtes Beispiel ist Google Maps, das häufig Grafiken verwendet, um Richtungen auf der ganzen Welt anzuzeigen.
Fazit
Ein Graph ist eine beliebte und häufig verwendete Datenstruktur, die neben anderen Bereichen viele Anwendungen im Bereich der Informatik selbst hat. Diagramme bestehen aus Scheitelpunkten und Kanten, die zwei oder mehr Scheitelpunkte verbinden.
Ein Graph kann gerichtet oder ungerichtet sein. Wir können Diagramme unter Verwendung einer Adjazenzmatrix darstellen, die eine lineare Darstellung ist, sowie unter Verwendung einer Adjazenz-verknüpften Liste. In diesem Tutorial haben wir auch die Implementierung des Diagramms besprochen.
=> Hier finden Sie Informationen zur vollständigen Liste der C ++ - Tutorials.
Literatur-Empfehlungen
- Python Advanced List Tutorial (Listensortierung, Umkehren, Indexieren, Kopieren, Verbinden, Summen)
- Python-Liste - Elemente erstellen, darauf zugreifen, in Scheiben schneiden, hinzufügen oder löschen
- Standard-Router-IP-Adressliste für gängige WLAN-Router-Marken
- 12 besten Tools zur Erstellung von Liniendiagrammen zum Erstellen atemberaubender Liniendiagramme (2021 RANGLISTE)
- Standard-Router-Anmeldekennwort für Top-Router-Modelle (Liste 2021)
- Datenstruktur der verknüpften Liste in C ++ mit Abbildung
- Datenstruktur für zirkuläre verknüpfte Listen in C ++ mit Abbildung
- Doppelt verknüpfte Listendatenstruktur in C ++ mit Abbildung
