Breiten-Suchlabyrinth in C++

1. Breitensuchalgorithmus
2. Schritte zum Durchführen eines Breiten-Suchlabyrinths in C++

Eine Breitensuche ist ein Algorithmus zum Durchlaufen oder Durchsuchen von Baum- oder Diagrammdatenstrukturen. An jedem Knoten besucht der Algorithmus die Kinder, bevor er die Eltern besucht.

Mit anderen Worten, es erweitert sich von seiner aktuellen Position auf jeder Baumebene nach außen, anstatt sich nach oben zum Elternteil und nach unten zu seinen Kindern zu bewegen.

Die Breitensuche wird verwendet, um die kürzesten Wege auf Graphen zu finden. Es wurde verwendet, um Lösungen in vielen Bereichen wie künstlicher Intelligenz, Informatik, Mathematik und Sozialwissenschaften zu finden.

Breitensuchalgorithmus

Die Breitensuche ist ein Suchalgorithmus, der den Baum der Breite nach durchquert und die Knoten der Breite nach erweitert.

Der Algorithmus beginnt an einem beliebigen Knoten und erweitert alle seine Kinder. Dann fährt es fort, dasselbe für jedes seiner Kinder zu tun, und so weiter.

Der Prozess endet, wenn er einen Blattknoten erreicht oder einen Zielzustand findet.

Um den kürzesten Weg von einem Knoten zum anderen zu finden, müssen wir seine Entfernung von diesem Knoten kennen. Dies kann berechnet werden, indem die Kantenlängen zwischen zwei beliebigen Knoten im Diagramm addiert werden.

Schritte zum Durchführen eines Breiten-Suchlabyrinths in C++

Die Schritte zum Durchführen des Breiten-Suchlabyrinths in C++ sind wie folgt:

Wenn die Warteschlange nicht leer wird, nehmen wir ein Element daraus und rufen darauf rekursiv den Breitensuchalgorithmus auf, bis wir einen unerforschten Knoten erreichen.

Schließlich, wenn die Warteschlange leer wird, erreichen wir ein Ende des Labyrinths und hören auf, aus dieser Richtung nach unerforschten Knoten zu suchen.

Beispiel für das Breiten-Suchlabyrinth in C++

Dies ist ein Beispiel für ein Breiten-Suchlabyrinth in C++. Der Code implementiert den Algorithmus, um den kürzesten Weg von einem bestimmten Startknoten zu allen anderen Knoten in einem Diagramm zu finden.

#include <bits/stdc++.h>
using namespace std;
#define HORI 3
#define VERT 3
struct Point {
  int a;
  int b;
};
struct queueNode {
  Point de;
  int sam;
};
bool isValid(int hori, int vert) {
  return (hori >= 0) && (hori < HORI) && (vert >= 0) && (vert < VERT);
}
int horiNum[] = {9, 7, 9, 2};
int vertNum[] = {3, 3, 4, 5};
int BFS(int lk[][VERT], Point ace, Point hello) {
  if (!lk[ace.a][ace.b] || !lk[hello.a][hello.b]) return -1;
  bool visited[HORI][VERT];
  memset(visited, false, sizeof visited);
  visited[ace.a][ace.b] = true;
  queue<queueNode> e;
  queueNode s = {ace, 0};
  e.push(s);
  while (!e.empty()) {
    queueNode curr = e.front();
    Point de = curr.de;
    if (de.a == hello.a && de.b == hello.b) return curr.sam;
    e.pop();
    for (int i = 0; i < 4; i++) {
      int hori = de.a + horiNum[i];
      int vert = de.b + vertNum[i];
      if (isValid(hori, vert) && lk[hori][vert] && !visited[hori][vert]) {
        visited[hori][vert] = true;
        queueNode Adjcell = {{hori, vert}, curr.sam + 1};
        e.push(Adjcell);
      }
    }
  }
  return -1;
}
int main() {
  int lk[HORI][VERT] = {{3, 9, 2}, {4, 5, 3}, {0, 3, 0}};
  Point source = {0, 0};
  Point hello = {1, 1};
  int sam = BFS(lk, source, hello);
  if (sam != 1)
    cout << "Shortest Path:" << sam;
  else
    cout << "Failed!!!";
  return 0;
}

Klicken Sie hier, um die Funktion des Codes wie oben erwähnt zu überprüfen.