ค้นหาเส้นทางจากจุดสุดยอดหนึ่งจุดไปยังจุดพักโดยใช้ BFS ใน C++

ในปัญหานี้ เราได้รับกราฟกำกับที่แสดงเป็นรายการที่อยู่ติดกัน งานของเรา คือ สร้างโปรแกรมสำหรับค้นหาเส้นทางจากจุดยอดจุดหนึ่งไปยังจุดพักโดยใช้ BFS .

บีเอฟเอส (Breadth First Search) เป็นอัลกอริธึมที่เคลื่อนที่ข้ามกราฟในวงกว้างและใช้คิวเพื่อจดจำจุดยอดถัดไปเพื่อเริ่มการค้นหา เมื่อจุดสิ้นสุดเกิดขึ้นในการวนซ้ำใดๆ

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล −

ผลผลิต

ส

เอ <=ส

B <=A <=S

ค <=ส

D <=C <=S

แนวทางการแก้ปัญหา

ในการแก้ปัญหา เราจะดำเนินการอัลกอริทึมการค้นหา BFS ในแต่ละองค์ประกอบของกราฟ ในการปฏิบัติงาน เราจะสร้างคิวที่จะจัดเก็บแฟล็กสำหรับการเยี่ยมชมโหนดใดๆ จากนั้น ใช้อาร์เรย์ที่เยี่ยมชม เราจะตรวจสอบว่าองค์ประกอบนั้นถูกเยี่ยมชมหรือไม่ (ค่าไบนารี 0 และ 1 หมายถึงการเยี่ยมชม)

ตอนนี้ เราจะทำการแก้ตัวอย่างทีละขั้นตอนเพื่อทำความเข้าใจการทำงานของโซลูชันของเรา

เริ่มจากโหนด S

• เราจะไปที่โหนด A โดยตรง

• ในการเข้าถึงโหนด B เราจะไปที่โหนด A ก่อน จากนั้นจึงไปถึงโหนด B ผ่านโหนด A

• เพื่อไปยังโหนด C เราจะไปที่ C จาก S โดยตรง

• ในการเข้าถึงโหนด D เราจะไปที่โหนด C ก่อนแล้วจึงไปที่โหนด D

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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