그래프에서 두 노드 사이의 경로를 찾는 C++ 프로그램

이 프로그램에서는 주어진 그래프에서 DFS를 사용하여 두 노드 사이에 경로가 존재하는지 확인할 수 있습니다.

알고리즘

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:
      //declaration of functions
      G(int n);
      void addEd(int v, int u);
      bool isReach(int s, int d);
};
G::G(int n) {
   this->n = n;
   adj = new list<int> [n];
}
void G::addEd(int v, int u) //add edges to the graph {
   adj[v].push_back(u);
}
bool G::isReach(int s, int d) {
   if (s == d)
      return true;
      //Mark all the vertices as unvisited.
      bool *visited = new bool[n];
   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 an adjacent has not been visited, then mark it visited and enqueue it
      for (i = adj[s].begin(); i != adj[s].end(); ++i) {
         if (*i == d)
            return true;
            // If this adjacent node is the destination node, then return true else continue to BFS
         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