資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 中的 BFS 查詢從一個頂點到其餘頂點的路徑
在這個問題中，我們得到一個用鄰接表表示的有向圖。**我們的任務**是_建立一個程式，使用 BFS 查詢從一個頂點到其餘頂點的路徑_。
BFS(廣度優先搜尋) 是一種以廣度優先的方式遍歷圖的演算法，它使用佇列來記住在任何迭代中遇到死衚衕時要獲取下一個頂點以開始搜尋。
讓我們舉個例子來理解這個問題：
輸入 −
輸出
S
A <= S
B <= A <= S
C <= S
D <= C <= S
解決方案方法
為了解決這個問題，我們將對圖的每個元素執行 BFS 搜尋演算法。為了執行此任務，我們將建立一個佇列，該佇列將儲存對任何節點的訪問標誌。然後，使用一個訪問陣列，我們將檢查元素是否被訪問過（二進位制值 0 和 1 表示訪問）。
現在，我們將逐步解決示例，以瞭解我們解決方案的工作原理：
從節點 S 開始：
我們將直接訪問節點 A。
要到達節點 B，我們將首先訪問節點 A，然後遍歷節點 A 到達節點 B。
要到達節點 C，我們將直接從 S 訪問 C。
要到達節點 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
更新於：2022年2月1日
498 次瀏覽
廣告