数据结构
网络
关系数据库管理系统 (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 次浏览
