주어진 2개의 노드 사이에 경로가 존재하는지 확인하는 C++ 프로그램

이것은 주어진 2개의 노드 사이에 경로가 존재하는지 확인하는 C++ 프로그램입니다.

알고리즘

Begin
   function isReach() is a recursive function to check whether d is reachable to s:
   A) Mark all the vertices as unvisited.
   B) Mark the current node as visited and enqueue it and it will be used to get all adjacent vertices of a vertex.
   C) Dequeue a vertex from queue and print it.
   D) Get all adjacent vertices of the dequeued vertex s.
   E) If an adjacent has not been visited, then mark it visited and enqueue it.
   F) If this adjacent node is the destination node, then return true else continue to BFS.
End

예시

#include <iostream>
#include <list>
using namespace std;
class G {
   int n;
   list<int> *adj;
   public:
      G(int n);
      void addEd(int x, int w);
      bool isReach(int s, int d);
};
G::G(int n) { //constructor 
   this->n = n;
   adj = new list<int> [n];
}
void G::addEd(int x, int w) { //adding edge to the graph
   adj[x].push_back(w); //ad w to x’s list
}
bool G::isReach(int s, int d) {
   if (s == d)
   return true;
   bool *visited = new bool[n];
   //Mark all the vertices as unvisited.
   for (int i = 0; i < n; i++)
      visited[i] = false;
   list<int> queue;
   //Mark the current node as visited and enqueue it and it will be used to get all adjacent vertices of a vertex
   visited[s] = true;
   queue.push_back(s);
   list<int>::iterator i;
   while (!queue.empty()) {
      s = queue.front();
      queue.pop_front(); //Dequeue a vertex from queue and print it
      //If a adjacent has not been visited,
      for (i = adj[s].begin(); i != adj[s].end(); ++i) {
         if (*i == d)
            return true;
         if (!visited[*i]) {
            visited[*i] = true;
            queue.push_back(*i);
         }
      }
   }
   return false;
}
int main() {
   G g(4);
   g.addEd(1, 3);
   g.addEd(0, 1);
   g.addEd(2, 3);
   g.addEd(1, 0);
   g.addEd(2, 1);
   g.addEd(3, 1);
   cout << "Enter the source and destination vertices: (0-3)";
   int a, b;
   cin >> a >> b;
   if (g.isReach(a, b))
      cout << "\nThere is a path from " << a << " to " << b;
   else
      cout << "\nThere is no path from " << a << " to " << b;
   int t;
   t = a;
   a = b;
   b= t;
   if (g.isReach(a, b))
      cout << "\nThere is a path from " << a << " to " << b;
   else
      cout << "\nThere is no path from " << a << " to " << b;
   return 0;
}

출력

Enter the source and destination vertices: (0-3)
There is a path from 3 to 1
There is a path from 1 to 3