資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究不使用佇列的廣度優先搜尋
廣度優先搜尋(BFS)是一種用於以廣度優先方式遍歷圖中節點的圖遍歷演算法。BFS 的常見實現使用佇列資料結構來跟蹤要訪問的節點。但是，可以使用其他資料結構來實現 BFS，而無需顯式使用佇列。
一種無需佇列實現 BFS 的替代方法是使用兩個陣列或列表：一個用於當前正在遍歷的節點層，另一個用於下一層要遍歷的節點。最初，當前層列表僅包含源節點。
該演算法首先迭代當前層列表並訪問每個節點。對於每個訪問的節點，都會檢查其相鄰節點。如果相鄰節點尚未訪問，則將其標記為已訪問並新增到下一層列表中。這個過程持續到當前層列表中的所有節點都已訪問。
一旦完全遍歷了當前層列表，演算法就會繼續到下一層列表並重復訪問節點和更新下一層列表的過程。這個過程持續到沒有未訪問的節點為止。
使用的方法
廣度優先方法
廣度優先方法
BFS 演算法從源節點開始，遍歷其鄰居，然後移動到鄰居的下一層。使用集合資料結構跟蹤訪問的節點。在每個迴圈中，演算法訪問一個節點，將其標記為已訪問，並將未訪問的相鄰節點入隊。此過程持續到訪問所有可達節點。
程式碼初始化一個向量 adj 來表示圖的鄰接表。向量的每個元素對應一個節點，每個元素的值包含其相鄰節點。BFS 遍歷由 BFS 函式執行，該函式接受源節點、節點數 N、已訪問節點的向量 vis、距離 dp 和一個向量 v 來跟蹤要訪問的節點。bfsTraversal 函式初始化已訪問和距離向量，然後呼叫 BFS 函式執行遍歷。
演算法
建立圖的鄰接表表示。
初始化一個佇列來儲存要訪問的節點。
初始化一個已訪問陣列來跟蹤已訪問的節點。
初始化一個距離陣列來儲存從源節點到每個節點的距離。將源節點的距離設定為 0。
將源節點入隊並將其標記為已訪問。
當佇列不為空時，執行以下操作：
出隊佇列頭部的節點。對於每個已出隊的且尚未訪問的相鄰節點，執行以下操作：將相鄰節點入隊。將相鄰節點標記為已訪問。更新相鄰節點的距離為已出隊節點的距離加 1。
重複步驟 6 直到佇列為空。
BFS 遍歷完成後，距離陣列將包含從源節點到圖中所有其他節點的距離。
可選地，您還可以在 BFS 遍歷期間跟蹤每個節點的父節點，以構建從源節點到所有其他節點的最短路徑。
示例
#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;
void bfsTraversal(int adjacencyList[][2], int numVertices, int source) {
bool visited[numVertices + 1] = {false};
int distances[numVertices + 1] = {0};
queue<int> vertices;
vertices.push(source);
visited[source] = true;
while (!vertices.empty()) {
int node = vertices.front();
cout << node << ", ";
vertices.pop();
for (int i = 0; i < 2; i++) {
int next = adjacencyList[node][i];
if (!visited[next]) {
vertices.push(next);
distances[next] = distances[node] + 1;
visited[next] = true;
}
}
}
}
int main() {
int adjacencyList[][2] = {{0, 0}, {1, 2}, {3, 4}, {0, 0}, {0, 0}};
int numVertices = 4;
int source = 2;
bfsTraversal(adjacencyList, numVertices, source);
return 0;
}
輸出
2,3,4,0
示例
#include <iostream>
#include <vector>
using namespace std;
void bfsTraversal(vector<vector<int>>& adjacencyList, int N, int source) {
vector<bool> visited(N + 1, false);
vector<int> distances(N + 1, 0);
vector<int> vertices;
vertices.push_back(source);
visited[source] = true;
int curr = 0;
while (curr < vertices.size()) {
int node = vertices[curr];
cout << node << ", ";
for (int i = 0; i < adjacencyList[node].size(); i++) {
int next = adjacencyList[node][i];
if (!visited[next]) {
vertices.push_back(next);
distances[next] = distances[node] + 1;
visited[next] = true;
}
}
curr++;
}
cout << "\nDistances from source " << source << ":\n";
for (int i = 1; i <= N; i++) {
cout << "Node " << i << ": " << distances[i] << endl;
}
}
int main() {
int N = 8;
vector<vector<int>> adjacencyList(N + 1);
adjacencyList[0] = {1, 2};
adjacencyList[1] = {2};
adjacencyList[2] = {0, 3};
adjacencyList[3] = {3};
adjacencyList[4] = {5};
adjacencyList[5] = {6, 7};
adjacencyList[6] = {};
adjacencyList[7] = {};
adjacencyList[8] = {};
int source = 5;
bfsTraversal(adjacencyList, N, source);
return 0;
}
輸出
5, 6, 7, Distances from source 5: Node 1: 0 Node 2: 0 Node 3: 0 Node 4: 0 Node 5: 0 Node 6: 1 Node 7: 1 Node 8: 0
結論
本文解釋瞭如何在不使用佇列資料結構的情況下實現廣度優先搜尋 (BFS) 演算法。BFS 演算法通常用於以逐層方式遍歷圖，從給定的源節點開始。通常，使用佇列來儲存要訪問的節點。但是，本文探討了一種使用簡單的列表或陣列來儲存下一層節點的替代方法。
這種替代實現實現了圖的廣度優先遍歷。本文概述了 BFS 演算法的步驟，例如初始化鄰接表、維護已訪問和距離陣列，以及使用迴圈迭代節點層。它還提供了一個 C 程式碼示例，演示瞭如何在不使用佇列的情況下進行 BFS 遍歷。程式碼準確地遍歷圖，列印 BFS 遍歷序列，並計算從源節點到所有其他節點的距離。總的來說，本文清晰地解釋並提供了 BFS 演算法的實際實現，該實現不使用佇列，展示了一種以廣度優先方式遍歷圖的替代方法。
413 次瀏覽
