Chương trình C ++ để tìm đường dẫn giữa hai nút trong biểu đồ

Trong Chương trình này, chúng ta có thể tìm xem có tồn tại đường dẫn giữa hai nút hay không bằng cách sử dụng DFS trên đồ thị đã cho.

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

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