C ++程序在图中找到两个节点之间的路径

在此程序中，我们可以通过在给定图上使用DFS来找出两个节点之间是否存在路径。

算法

Begin
   function isReach() is a recursive function to check whether d is reachable to s :
   A) 将所有顶点标记为未访问。
   B) 将当前节点标记为已访问并使其入队，它将用于获取顶点的所有相邻顶点
   C) Dequeue a vertex from queue and print it
   D) Get all adjacent vertices of the dequeued vertex s
   E) 如果尚未访问相邻对象，则将其标记为已访问并排队
   F)如果此相邻节点是目标节点，则返回true，否则继续执行BFS-
End

示例

#include <iostream>
#include <list>
using namespace std;
class G {
   int n;
   list<int> *adj;
   public:
      //功能声明
      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;
      //将所有顶点标记为未访问。
      bool *visited = new bool[n];
   for (int i = 0; i < n; i++)
      visited[i] = false;
      list<int> queue;
      //将当前节点标记为已访问并使其入队，它将用于获取顶点的所有相邻顶点
      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
      //如果尚未访问相邻对象，则将其标记为已访问并排队
      for (i = adj[s].begin(); i != adj[s].end(); ++i) {
         if (*i == d)
            return true;
            //如果此相邻节点是目标节点，则返回true，否则继续执行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