ในปัญหานี้ เราจะได้รับกราฟกำกับ และเราต้องพิมพ์เส้นทางทั้งหมดจากต้นทางไปยังปลายทางของกราฟโดยใช้การค้นหาแบบกว้างก่อน (BFS)
กราฟกำกับ เป็นกราฟที่มีขอบที่ชี้จากจุดยอด a ถึง b
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน -
ต้นทาง =K ปลายทาง =P
ผลผลิต
K -> T -> Y -> A -> P K -> T -> Y -> P K -> A -> P
ที่นี่เราพบเส้นทางจาก K ถึง P เราได้สำรวจเส้นทางและพิมพ์เส้นทางทั้งหมดจาก K ที่นำเราไปยัง P.
ในการพิมพ์เส้นทางทั้งหมดจากต้นทางไปยังปลายทาง เราจะต้องสำรวจกราฟและเก็บเส้นทาง จากนั้นพิมพ์เส้นทางที่ถูกต้อง
ในกรณีของการใช้ DFS กระบวนการนั้นง่าย แต่ในกรณีนี้ค่อนข้างยุ่งยากในการนำไปใช้
เพื่อแก้ปัญหานี้ เราจำเป็นต้องมีคิวที่จะเก็บเส้นทาง เริ่มจากโหนดต้นทาง เราจะเริ่มสำรวจอาร์เรย์โดยใช้ BFS สำรวจ
ต้นไม้แล้วตรวจสอบในคิว หากถึงจุดยอดปลายทาง ให้พิมพ์องค์ประกอบคิว มิฉะนั้น ให้ข้ามไป
ตัวอย่าง
โปรแกรมด้านล่างจะทำให้การแก้ปัญหาชัดเจนยิ่งขึ้น -
#include <bits/stdc++.h>
using namespace std;
void printPath(vector<char>& path) {
int size = path.size();
for (int i = 0; i < size; i++)
cout<<path[i]<<" ";
cout<<endl;
}
int isVertexVisited(char x, vector<char>& path) {
int size = path.size();
for (int i = 0; i< size; i++)
if (path[i] == x)
return 1;
return 0;
}
void pathSourceToDestination(vector<vector<char> >&g, char src, char dst, int v) {
queue<vector<char> > q;
vector<char> path;
path.push_back(src);
q.push(path);
while (!q.empty()) {
path = q.front();
q.pop();
char last = path[path.size() - 1];
if (last == dst)
printPath(path);
for (int i = 0; i < g[last].size(); i++) {
if (!isVertexVisited(g[last][i], path)) {
vector<char> newpath(path);
newpath.push_back(g[last][i]);
q.push(newpath);
}
}
}
}
int main() {
vector<vector<char> > g;
int v = 4;
g.resize(4);
g['X'].push_back('S');
g['X'].push_back('A');
g['X'].push_back('N');
g['A'].push_back('S');
g['N'].push_back('X');
g['N'].push_back('A');
char src = 'N', dst = 'S';
cout<<"path from src "<<src<<" to dst "<<dst<<" are \n";
pathSourceToDestination(g, src, dst, v);
return 0;
} ผลลัพธ์
path from src N to dst S are N X S N A S N X A S
