数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用C++中的BFS打印从给定源到目标的所有路径
在这个问题中，我们给定一个有向图，我们必须使用广度优先搜索 (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
更新于：2020年7月14日
1K+ 浏览量
广告