Bei einem gegebenen Diagramm implementiert ein C-Programm die Tiefensuche (DFS) mithilfe einer Adjazenzmatrix

Einführung

Die Graphentheorie ermöglicht es uns, Beziehungen zwischen Objekten oder Entitäten zu untersuchen und zu visualisieren. In der aktuellen Informatiktechnologie spielt das Durchlaufen von Graphen eine entscheidende Rolle bei der Erforschung und Analyse verschiedener Arten von Datenstrukturen. Eine der wichtigsten Operationen, die in einem Diagramm ausgeführt werden, ist das Durchlaufen – das Folgen eines bestimmten Pfads, um alle Eckpunkte oder Knoten zu besuchen. Die auf einem Tiefenansatz basierende DFS-Durchquerung ermöglicht es uns, die Tiefe des Diagramms zu erkunden, bevor wir zurückgehen und andere Zweige erkunden. In diesem Artikel implementieren wir die DFS-Traversierung mithilfe der Adjazenzmatrixdarstellung in C.

Verwendung der Adjazenzmatrix für die DFS-Durchquerung

Ein Graph besteht aus zwei Hauptkomponenten, den Eckpunkten oder Knoten, die Entitäten oder Elemente darstellen, und den Kanten, die diese Eckpunkte verbinden und die Beziehungen zwischen ihnen beschreiben.

Die einzige Möglichkeit, die Beziehung zwischen Eckpunkten in einem gewichteten oder ungewichteten Diagramm darzustellen, ist eine Adjazenzmatrix. Sie hat normalerweise die Form einer quadratischen Matrix, in der Zeilen Quellscheitelpunkte und Spalten Zielscheitelpunkte darstellen und jede Zelle Informationen über die Existenz oder das Gewicht einer Kante zwischen entsprechenden Paaren enthält.

Beispiel

Die Eingabe erfolgt über einen bestimmten Satz von Elementen unter Verwendung der vier Eckpunkte des Diagramms. Die Eingabe ist:

1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

Angenommen, der Startscheitelpunkt des Diagramms ist 2. Der Graph wird ab dem Scheitelpunkt „2“ durchlaufen. Die benachbarten Scheitelpunkte des Scheitelpunkts „2“ sind offensichtlich 1 und 3. Da der Startscheitelpunkt 2 ist, kann während des Durchlaufs nicht erneut auf ihn zugegriffen werden. Scheitelpunkt 3 wird nach Scheitelpunkt 2 besucht, dann müssen wir die benachbarten Scheitelpunkte 1 und 2 von Scheitelpunkt 3 überprüfen. Scheitelpunkt 1 und Scheitelpunkt 2 wurden besucht und die Durchquerung stoppt.

Methode 1: C-Programm mit DFS-Traversierung unter Verwendung der Adjazenzmatrix als Eingabe in das gegebene Diagramm

Die Eingabe wird mit einigen Zahlen definiert und mithilfe einer for-Schleife wird die Adjazenzmatrix iteriert und die DFS-Durchquerung zurückgegeben.

Algorithmus

Schritt 1: Das Programm definiert zunächst eine Konstante „MAX“, um die maximale Anzahl von Knoten im angegebenen Diagramm darzustellen, und initialisiert ein Array mit dem Namen „visited“, um zu verfolgen, ob ein bestimmter Knoten während der Durchquerung besucht wurde.

Schritt 2: Die Funktion „dfs()“ verwendet eine quadratische Adjazenzmatrix als Parameter, „adjMatrix“ stellt unseren Graphen dar, die Gesamtzahl der Scheitelpunkte ist „vCount“ und der Startscheitelpunkt ist „start“. Diese Funktion führt eine rekursive Tiefensuche durch den angegebenen Graphen durch.

Schritt 3: In der Funktion „dfs()“ markieren wir jeden aktuell verarbeiteten Scheitelpunkt als „besucht“, indem wir den Index im booleschen basierten Array „visited[]“ verwenden und ihn entsprechend ausdrucken.

Schritt 4: Die Schleife in „dfs()“ iteriert rekursiv alle nicht besuchten Nachbarn des aktuellen Knotens, bis es unmöglich ist, einen Scheitelpunkt mit ihm zu verbinden.

Schritt 5: In main() verwenden wir eine verschachtelte Schleife, um die Eingaben des Benutzers einzulesen, beispielsweise die Anzahl der Scheitelpunkte von „vCount“ und ihre entsprechenden Verbindungen in die Adjazenzmatrix.

Schritt 6: Anschließend fragen wir den Benutzer nach dem gewünschten Startscheitelpunkt und initialisieren dann jedes Element des Arrays „visited[]“ auf Null (da noch keine Knoten besucht wurden).

Schritt 7: Abschließend ruft das Programm die Funktion „dfs()“ mit den entsprechenden Parametern auf, um die Tiefensuchdurchquerung zu starten, und druckt den DFS-Durchquerungspfad aus.

Beispiel

//Including the required header files
#include<stdio.h>
#define MAX 100

int visited[MAX];
//dfs function is defined with three arguments
void dfs(int adjMatrix[][MAX], int vCount, int start) {
   visited[start] = 1;
   printf("%d ", start);

   for(int i=0; i<vCount; i++) {
      if(adjMatrix[start][i] && !visited[i]) {
         dfs(adjMatrix,vCount,i);
      }
   }
}
//main function is used to implement the above functions
int main() {
   int adjMatrix[MAX][MAX];
   int vCount;

   // Assigning the variable with value of 4
   vCount = 4;

   // Assigning the adjacency matrix directly same the example given above
   adjMatrix[0][0] = 1;
   adjMatrix[0][1] = 0;
   adjMatrix[0][2] = 0;
   adjMatrix[0][3] = 1;
   adjMatrix[1][0] = 0;
   adjMatrix[1][1] = 1;
   adjMatrix[1][2] = 1;
   adjMatrix[1][3] = 0;
   adjMatrix[2][0] = 0;
   adjMatrix[2][1] = 1;
   adjMatrix[2][2] = 1;
   adjMatrix[2][3] = 0;
   adjMatrix[3][0] = 1;
   adjMatrix[3][1] = 0;
   adjMatrix[3][2] = 0;
   adjMatrix[3][3] = 1;
//Declaring the start variable as integer data type and later assigned with a value of 2
   int start;
   
   // Assigning the starting vertex directly
   start = 2;
   
   for(int i = 0; i < MAX; ++i) {
      visited[i] = 0;
   }

   printf("\nDFS Traversal: ");
   dfs(adjMatrix, vCount, start);
   

   return 0;
}

Ausgabe

DFS Traversal: 2 1

Fazit

Durch die Verwendung der Adjazenzmatrix als Darstellung des Diagramms können wir DFS für große oder komplexe Datensätze effizient durchführen. In diesem Artikel erläutern wir dies ausführlich und schlagen ein C-Programm vor, das eine Tiefensuchdurchquerung mithilfe einer auf einer Adjazenzmatrix basierenden Darstellung implementiert. Die Tiefensuche ist ein leistungsstarker Algorithmus zum Erkunden und Analysieren von Diagrammstrukturen.

Das obige ist der detaillierte Inhalt vonBei einem gegebenen Diagramm implementiert ein C-Programm die Tiefensuche (DFS) mithilfe einer Adjazenzmatrix. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!