सी ++ में बीएफएस का उपयोग करके एक शीर्ष से आराम करने के लिए पथ ढूँढना

इस समस्या में, हमें एक निर्देशित ग्राफ दिया गया है जो एक आसन्न सूची के रूप में दर्शाया गया है। हमारा कार्य बीएफएस का उपयोग करके एक शीर्ष से आराम करने के लिए पथ खोजने के लिए एक प्रोग्राम बनाने के लिए है ।

बीएफएस (ब्रेडथ फर्स्ट सर्च) एक एल्गोरिथम है जो एक ग्राफ़ को चौड़ाई की गति में ट्रेस करता है और किसी भी पुनरावृत्ति में एक मृत अंत होने पर खोज शुरू करने के लिए अगला शीर्ष प्राप्त करने के लिए याद रखने के लिए एक कतार का उपयोग करता है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट -

आउटपुट

एस

ए <=एस

बी <=ए <=एस

सी <=एस

डी <=सी <=एस

समाधान दृष्टिकोण

समस्या को हल करने के लिए, हम ग्राफ़ के प्रत्येक तत्व पर BFS खोज एल्गोरिथम का प्रदर्शन करेंगे। कार्य करने के लिए, हम एक कतार बनाएंगे जो किसी भी नोड पर जाने के लिए ध्वज को संग्रहीत करेगी। फिर, एक विज़िट किए गए सरणी का उपयोग करके हम जांच करेंगे कि तत्व का दौरा किया गया है या नहीं (द्विआधारी मान 0 और 1 विज़िट को दर्शाते हैं)।

अब, हम अपने समाधान की कार्यप्रणाली को समझने के लिए उदाहरण को चरण दर चरण हल करेंगे,

नोड एस से शुरू,

• हम सीधे नोड ए पर जाएंगे।

• नोड बी तक पहुंचने के लिए, हम पहले नोड ए पर जाएंगे, फिर नोड बी ट्रैवर्सिंग नोड ए पर पहुंचेंगे।

• नोड सी तक पहुंचने के लिए, हम सीधे एस से सी पर जाएंगे।

• नोड डी तक पहुंचने के लिए, हम पहले नोड सी और फिर नोड डी पर जाएंगे।

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम

#include <bits/stdc++.h>
using namespace std;
void printPath(vector<int> parent, int initial, int node){
   while (initial != node){
      cout<<node<<" <= ";
      node = parent[node];
   }
   cout<<node<<endl;
}
void findPathBFS(vector<vector<int> > graphAdjList, int initial, int graphSize){
   vector<int> parent(graphSize, 0);
   vector<int> queue(graphSize, 0);
   int front = -1, rear = -1;
   vector<int> isVisited(graphSize, 0);
   isVisited[0] = 1;
   parent[0] = initial;
   queue[++rear] = initial;
   int k;
   while (front != rear)
   {
      k = queue[++front];
      for (int j:graphAdjList[k]){
         if (isVisited[j] == 0){
            queue[++rear] = j;
            isVisited[j] = 1;
            parent[j] = k;
         }
      }
   }
   for (k = 0; k < graphSize; k++)
      printPath(parent, initial, k);
}
int main(){
   vector<vector<int> > graphAdjList;
   graphAdjList.push_back({1, 3});
   graphAdjList.push_back({0, 2});
   graphAdjList.push_back({1});
   graphAdjList.push_back({4});
   graphAdjList.push_back({0});
   int graphSize = graphAdjList.size();
   int initial = 0;
   cout<<"The Path from vertex '0' to all other vertex in the graph is : \n";
   findPathBFS(graphAdjList, initial, graphSize);
}

आउटपुट

The Path from vertex '0' to all other vertex in the graph is :
0
1 <= 0
2 <= 1 <= 0
3 <= 0
4 <= 3 <= 0