C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

グラフ内の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

  1. C++で二分木の2つのノード間の距離を見つける

    ノードが少ない二分木があると考えてください。 2つのノードuとvの間の距離を見つける必要があります。ツリーが次のようになっていると仮定します- これで、(4、6)=4の間の距離、パスの長さは4、(5、8)の間の長さ=5などになります。 この問題を解決するために、LCA(Lowest Common Ancestor)を見つけてから、LCAから2つのノードまでの距離を計算します。 例 #include<iostream> using namespace std; class Node {    public:       in

  2. C++プログラミングのバイナリツリー内の任意の2つのノード間のパスを出力します。

    個別のノードのバイナリツリーと、バイナリツリー内のパスを出力するバイナリツリーの2つのノードが与えられます。 例 −ノード140から211の間のパスを出力して、その出力が次のようになるようにします- Output: 140->3->10->211 アイデアは、ルートノードから2つのノードへのパスを見つけて、それらを2つの別々のベクトルまたは配列(path1とpath2など)に格納することです。 ここで、2つの異なるケースが発生します- 2つのノードがルートノードの異なるサブツリーにある場合 − 2つのノードが、1つが左に、もう1つが右のように異なるサブツリーにあ