資料結構
網路
關係資料庫管理系統 (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+ 瀏覽量
廣告