グラフ内の2つのノード間のパスを見つけるC++プログラム

このプログラムでは、特定のグラフでDFSを使用して、2つのノード間にパスが存在するかどうかを確認できます。

アルゴリズム

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