Finden Sie heraus, ob es in einem gerichteten Graphen einen Pfad zwischen zwei Eckpunkten gibt

In der Informatik und Graphentheorie basieren Lösungen für verschiedene reale Modellszenarien stark auf gerichteten Graphen. Diese speziellen Graphen bestehen aus Eckpunkten, die durch gerichtete Kanten verbunden sind, die auf andere Eckpunkte zeigen. Die Bestimmung, ob ein Pfad zwischen zwei angegebenen Punkten existiert, ist ein typisches schwieriges Problem bei der Verwendung gerichteter Graphen. In diesem Artikel untersuchen wir verschiedene Möglichkeiten, dieses Dilemma mithilfe von C++ zu lösen, einschließlich der für jeden Prozess erforderlichen Syntax, um sicherzustellen, dass alles leicht verständlich ist. Darüber hinaus werden wir die Algorithmen, die jede Methode veranschaulichen, detailliert beschreiben und zwei ausführbare Codebeispiele beifügen.

Grammatik

Bevor wir uns mit den Einzelheiten befassen, ist es wichtig, die Sprachstruktur zu verstehen, die der Methodik hier zugrunde liegt. Bevor wir also mit dem Codebeispiel fortfahren, überprüfen wir zunächst diese Syntax.

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph);

Algorithmus

Das Finden eines Pfades zwischen zwei Eckpunkten in einem gerichteten Graphen kann mit verschiedenen Techniken gelöst werden. Dieser Artikel konzentriert sich auf zwei weit verbreitete Methoden:

Methode 1: Tiefensuche (DFS)

• Erstellen Sie ein besuchtes Array, um besuchte Scheitelpunkte während der Durchquerung zu verfolgen.

• Alle Elemente des besuchten Arrays auf „false“ initialisieren.

• StartVertex als besucht markieren.

• Wenn der Startscheitelpunkt und der Endscheitelpunkt identisch sind, wird true zurückgegeben, was darauf hinweist, dass ein Pfad vorhanden ist.

• Verwenden Sie für jeden benachbarten Scheitelpunkt des aktuellen Scheitelpunkts den benachbarten Scheitelpunkt als neuen Startscheitelpunkt und rufen Sie die Funktion isPathExists rekursiv auf.

• Gibt true zurück, wenn ein rekursiver Aufruf true zurückgibt.

• Wenn kein rekursiver Aufruf „true“ zurückgibt, geben Sie „false“ zurück.

Methode 2: Breitensuche (BFS)

• Erstellen Sie ein besuchtes Array, um besuchte Scheitelpunkte während der Durchquerung zu verfolgen.

• Alle Elemente des besuchten Arrays auf false initialisieren.

• Erstellen Sie eine Warteschlange zum Speichern ausstehender Scheitelpunkte.

• StartVertex zur Warteschlange hinzufügen und als besucht markieren.

• Wenn die Warteschlange nicht leer ist, gehen Sie wie folgt vor:

• Entfernen Sie einen Scheitelpunkt aus der Warteschlange.

• Wenn der aus der Warteschlange entfernte Scheitelpunkt mit endVertex identisch ist, wird true zurückgegeben, was darauf hinweist, dass ein Pfad vorhanden ist.

• Für jeden Scheitelpunkt neben dem aus der Warteschlange entfernten Scheitelpunkt: Wenn er noch nicht besucht wurde, stellen Sie ihn in die Warteschlange und markieren Sie ihn als besucht.

• Gibt false zurück, wenn die Warteschlange leer wird und kein Pfad gefunden wird.

Beispiel 1: Methode der Tiefensuche (DFS)

#include <iostream>
#include <vector>
using namespace std;

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph) {
   vector<bool> visited(graph.size(), false);
   visited[startVertex] = true;
  
   if (startVertex == endVertex)
      return true;
  
   for (int adjVertex : graph[startVertex]) {
      if (!visited[adjVertex] && isPathExists(adjVertex, endVertex, graph))
         return true;
   }
  
   return false;
}

int main() {
   // Example usage
   int numVertices = 6;
   vector<vector<int>> graph(numVertices);
   graph[0] = {1, 2};
   graph[1] = {3};
   graph[2] = {1};
   graph[3] = {4, 5};
   graph[4] = {};
   graph[5] = {4};

   int startVertex = 0;
   int endVertex = 5;

   if (isPathExists(startVertex, endVertex, graph))
      cout << "A path exists between " << startVertex << " and " << endVertex << endl;
   else
      cout << "No path exists between " << startVertex << " and " << endVertex << endl;

   return 0;
}

Ausgabe

A path exists between 0 and 5

Der Code beginnt mit der Definition einer Funktion namens isPathExists, die startVertex, endVertex und einen durch eine Adjazenzliste dargestellten Graphen als Parameter akzeptiert. Es initialisiert einen booleschen Vektor namens „visited“, der die besuchten Scheitelpunkte verfolgt. Beim Ausführen dieser Funktion prüft sie zunächst, ob startVertex und endVertex identisch sind, indem sie sie vergleicht.

Wenn diese Eckpunkte in diesem Kontext vollständig übereinstimmen, gibt die Funktion sofort true zurück.

Wenn dies nicht der Fall ist und sie sich voneinander unterscheiden, wird eine weitere Maßnahme ergriffen, um die Nachbarschaft zwischen ihnen zu überprüfen und festzustellen, ob es einen Pfad zwischen ihnen gibt.

Dieser Prozess umfasst die wiederholte Iteration der benachbarten Scheitelpunkte des Startscheitelpunkts. Bei jeder Iteration wird der neu gesuchte Scheitelpunkt als neuer Startpunkt verwendet und weiterhin nach verfügbaren Pfaden gesucht, indem „isPathExists“ rekursiv aufgerufen wird. Dieser Zyklus wiederholt sich, bis alle möglichen Pfade ausgeschöpft sind oder ein erfolgreicher Pfad gefunden wird.

Wenn einer dieser wiederholten Aufrufe eine potenzielle Kante erkennt, die den Startknoten und den Endknoten verbindet, bedeutet das Ergebnis dieser Filterung, dass tatsächlich eine nutzbare Verbindung zwischen diesen beiden Knoten besteht. Daher wird True sofort zurückgegeben.

Andernfalls wird eine ausfallsichere Schleifenaktion eingeleitet, wenn die im Algorithmus festgelegte Komplexität dazu führt, dass keine Route verfügbar ist. Im Falle eines solchen Ergebnisses gibt es „False“ zurück und bedauert, dass die Verbindung zwischen den Knoten fehlgeschlagen ist.

Beispiel 2: Methode der Breitensuche (BFS)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph) {
   vector<bool> visited(graph.size(), false);
   visited[startVertex] = true;
  
   queue<int> verticesQueue;
   verticesQueue.push(startVertex);
  
   while (!verticesQueue.empty()) {
      int currVertex = verticesQueue.front();
      verticesQueue.pop();
  
      if (currVertex == endVertex)
         return true;
  
      for (int adjVertex : graph[currVertex]) {
         if (!visited[adjVertex]) {
            visited[adjVertex] = true;
            verticesQueue.push(adjVertex);
         }
      }
   }
  
   return false;
}

int main() {
   // Example usage
   int numVertices = 6;
   vector<vector<int>> graph(numVertices);
   graph[0] = {1, 2};
   graph[1] = {3};
   graph[2] = {1};
   graph[3] = {4, 5};
   graph[4] = {};
   graph[5] = {4};

   int startVertex = 0;
   int endVertex = 5;

   if (isPathExists(startVertex, endVertex, graph))
      cout << "A path exists between " << startVertex << " and " << endVertex << endl;
   else
      cout << "No path exists between " << startVertex << " and " << endVertex << endl;

   return 0;
}

Ausgabe

A path exists between 0 and 5

Dieser Code definiert eine isPathExists-Funktion, die startVertex, endVertex und den durch die Adjazenzliste dargestellten Graphen als Parameter akzeptiert. Es initialisiert einen booleschen Vektor namens „visited“, um die besuchten Scheitelpunkte zu verfolgen, und eine Warteschlange namens „verticesQueue“, um ausstehende Scheitelpunkte zu speichern.

Die Funktion beginnt damit, dass startVertex in die Warteschlange gestellt und als besucht markiert wird. Der Betrieb unseres Algorithmus beginnt mit dem Eintritt in eine iterative Schleife, die so lange fortgesetzt wird, wie sich Elemente in ihrer Verarbeitungswarteschlangenstruktur befinden. Während diese strukturierte Iteration fortschreitet, werden in jedem Zyklus zwei Prüfungen durchgeführt: Zuerst wird überprüft, ob der aus der Warteschlange entfernte Scheitelpunkt der aktuellen Iteration mit dem in der vorherigen Ausführung angegebenen Zielendpunkt übereinstimmt. Wenn die beiden erfolgreich übereinstimmen, wird „true“ zurückgegeben, andernfalls wird mit dem nächsten Schritt fortgefahren um nahegelegene Randpunkte zu erkunden. Während dieses Erkundungsprozesses werden alle benachbarten, nicht erkundeten Scheitelpunkte als „besucht“ markiert, bevor sie zur tieferen Iteration und Prüfung in die Warteschlange gestellt werden, um zu sehen, ob sie mit endVertex übereinstimmen.

Nachdem alle Untersuchungen und Überprüfungen erfolgreich waren und der Warteschlange nichts hinzugefügt wurde, gibt die Funktion „false“ zurück.

Fazit

In der Entwicklung der Informatik kann die Komplexität der Navigation in gerichteten Graphen ein grundlegendes Problem darstellen. Um diese Herausforderungen zu bewältigen, besteht eines unserer Ziele darin, zwei gängige Ansätze zu untersuchen, die mit C++ implementiert werden. Die Tiefensuche (DFS) und die Breitensuche (BFS) stehen an der Spitze dieser Techniken und bieten Schritt-für-Schritt-Verfahren und funktionierende Codebeispiele, die jeden Algorithmus veranschaulichen. Sobald diese Methoden beherrscht werden, erschließen sie neues Potenzial bei der Bewältigung von Wegfindungshindernissen in verschiedenen Umgebungen (z. B. beim Routing von Netzwerken oder bei der Analyse sozialer Konnektivitätsrahmen) und dienen als wertvolle Ausgangspunkte in der Verbesserungsentwicklungsphase.

Das obige ist der detaillierte Inhalt vonFinden Sie heraus, ob es in einem gerichteten Graphen einen Pfad zwischen zwei Eckpunkten gibt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!