이 문제에서 방향 그래프가 주어지고 BFS(Breadth First Search)를 사용하여 소스에서 그래프의 대상까지의 모든 경로를 인쇄해야 합니다.
방향성 그래프 정점 a에서 b로 향하는 모서리가 있는 그래프입니다.
문제를 이해하기 위해 예를 들어 보겠습니다. -
소스 =K 대상 =P
출력
K -> T -> Y -> A -> P K -> T -> Y -> P K -> A -> P
여기에서 K에서 P로 가는 경로를 찾았습니다. 경로를 가로질러 K에서 P로 향하는 모든 경로를 인쇄했습니다.
소스에서 목적지까지의 모든 경로를 인쇄하려면 그래프를 트래버스하고 경로를 저장한 다음 유효한 경로를 인쇄해야 합니다.
DFS를 사용하는 경우 프로세스는 간단하지만 이 경우 구현하기가 약간 까다롭습니다.
이 문제를 해결하려면 경로를 저장할 큐가 필요합니다. A 소스 노드에서 시작하여 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