Inhaltsverzeichnis
Grammatik
Algorithmus
Methode 1: Tiefensuche (DFS)
Methode 2: Breitensuche (BFS)
Beispiel 1: Methode der Tiefensuche (DFS)
Ausgabe
Beispiel 2: Methode der Breitensuche (BFS)
Fazit
Heim Backend-Entwicklung C++ Finden Sie heraus, ob es in einem gerichteten Graphen einen Pfad zwischen zwei Eckpunkten gibt

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

Aug 29, 2023 pm 12:49 PM
顶点 路径判断 有向图

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.

1

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

Nach dem Login kopieren

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)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

#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;

}

Nach dem Login kopieren

Ausgabe

1

A path exists between 0 and 5

Nach dem Login kopieren
Nach dem Login kopieren

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)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

#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;

}

Nach dem Login kopieren

Ausgabe

1

A path exists between 0 and 5

Nach dem Login kopieren
Nach dem Login kopieren

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!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße Artikel -Tags

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

C Sprachfunktionsformat -Buchstaben -Fall -Konvertierungsschritte C Sprachfunktionsformat -Buchstaben -Fall -Konvertierungsschritte Mar 03, 2025 pm 05:53 PM

C Sprachfunktionsformat -Buchstaben -Fall -Konvertierungsschritte

Welche Werte sind von C -Sprachfunktionen zurückgegeben? Was bestimmt den Rückgabewert? Welche Werte sind von C -Sprachfunktionen zurückgegeben? Was bestimmt den Rückgabewert? Mar 03, 2025 pm 05:52 PM

Welche Werte sind von C -Sprachfunktionen zurückgegeben? Was bestimmt den Rückgabewert?

GULC: C -Bibliothek von Grund auf neu gebaut GULC: C -Bibliothek von Grund auf neu gebaut Mar 03, 2025 pm 05:46 PM

GULC: C -Bibliothek von Grund auf neu gebaut

Was sind die Definitionen und Aufrufregeln von C -Sprachfunktionen und was sind die? Was sind die Definitionen und Aufrufregeln von C -Sprachfunktionen und was sind die? Mar 03, 2025 pm 05:53 PM

Was sind die Definitionen und Aufrufregeln von C -Sprachfunktionen und was sind die?

Wie funktioniert die C -Standard -Vorlagenbibliothek (STL)? Wie funktioniert die C -Standard -Vorlagenbibliothek (STL)? Mar 12, 2025 pm 04:50 PM

Wie funktioniert die C -Standard -Vorlagenbibliothek (STL)?

eindeutiger Gebrauch und Phrasenfreigabe eindeutiger Gebrauch und Phrasenfreigabe Mar 03, 2025 pm 05:51 PM

eindeutiger Gebrauch und Phrasenfreigabe

Wo ist der Rückgabewert der C -Sprachfunktion im Speicher? Wo ist der Rückgabewert der C -Sprachfunktion im Speicher? Mar 03, 2025 pm 05:51 PM

Wo ist der Rückgabewert der C -Sprachfunktion im Speicher?

Wie benutze ich Algorithmen aus der STL (sortieren, finden, transformieren usw.) effizient? Wie benutze ich Algorithmen aus der STL (sortieren, finden, transformieren usw.) effizient? Mar 12, 2025 pm 04:52 PM

Wie benutze ich Algorithmen aus der STL (sortieren, finden, transformieren usw.) effizient?

See all articles