数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用 C++ 中的 BFS 算法计算树中给定层级的节点数
给定一个无向图，其中包含树的节点作为顶点。目标是使用 BFS（广度优先搜索）算法查找树中给定层级的节点数。
BFS 算法：
此算法逐层遍历图/树。从 0 层的节点开始，它将首先遍历 1 层中与其直接连接的所有节点，然后遍历下一层的所有节点，依此类推。
- 水平遍历当前层的节点。
- 以类似的方式遍历下一层的节点。
让我们通过示例来理解。
例如
输入 - level=2
输出 - 使用 BFS 算法计算树中给定层级的节点数为：1
说明 - 如上所示，图中所有层都只有一个节点。
输入 - level=1
输出 - 使用 BFS 算法计算树中给定层级的节点数为：2
说明 - 如上所示，图中所有层都只有一个节点。节点为 1, 2。
下面程序中使用的算法如下
在这种方法中，我们将遍历每个节点并将它们的层级设置为比其父节点高一级。我们将使用邻接表表示法来表示图。
如果起始节点为 0，则
level[0]=0,
level[1] = level[0]+1 = 1, level[2]=level[0]+1=1
level[3]= level[2]+1 = 2, level[4]=level[2]+1=2
- 创建一个名为 node 的类，表示具有数据（顶点数）和 next（指向邻接表的指针）的图。
- 公共方法 insert(int val, int point) 向图中添加边。
- 它将 val 添加到 point 的邻接表中，并将 point 添加到 val 的邻接表中。
- 函数 count_nodes(int a, int b) 返回从源节点 a 开始，b 层级的节点数。
- 将初始计数设置为 0。
- 获取布尔数组 check = new bool[data]。
- 数组 arr[data] 存储图中每个顶点的层级。
- 使用 for 循环将图的所有顶点设置为未访问，并设置 check[i] = false 和 arr[i] = 0。
- 为 BFS 遍历创建一个队列 l1。
- 将起始顶点标记为已访问，check[a] = true，并使用 l1.push_back(a) 将其添加到 l1 中，并将它的层级设置为 0。 arr[a] = 0。
- 当队列 l1 不为空时。
- 获取前一个元素 a = l1.front() 并使用 l1.pop_front() 打印它。
- 将 a 的所有相邻的未访问顶点标记为已访问，并添加到队列 l1。
- 将每个相邻顶点的层级设置为 a 的层级 + 1。
- 在 while 循环结束时，使用 for 循环遍历 arr[]，对于每个 arr[i] == b，递增计数。
- 最后返回计数作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
class node {
int data;
list < int > * next;
public:
node(int data) {
this -> data = data;
next = new list < int > [data];
}
void insert(int val, int point) {
next[val].push_back(point);
next[point].push_back(val);
}
int count_nodes(int a, int b);
};
int node::count_nodes(int a, int b) {
int count = 0;
bool * check = new bool[data];
int arr[data];
for (int i = 0; i < data; i++) {
check[i] = false;
arr[i] = 0;
}
list < int > l1;
check[a] = true;
l1.push_back(a);
arr[a] = 0;
while (!l1.empty()) {
a = l1.front();
l1.pop_front();
for (auto it = next[a].begin(); it != next[a].end(); ++it) {
if (!check[ * it]) {
arr[ * it] = arr[a] + 1;
check[ * it] = true;
l1.push_back( * it);
}
}
}
for (int i = 0; i < data; i++) {
if (arr[i] == b) {
count++;
}
}
return count;
}
int main() {
node n1(5);
n1.insert(1, 2);
n1.insert(0, 3);
n1.insert(1, 3);
n1.insert(2, 4);
int level = 1;
cout << "Count of number of nodes at given level in a tree using BFS are: " << n1.count_nodes(0, level);
return 0;
}如果我们运行上面的代码，它将生成以下输出：
输出
Count of number of nodes at given level in a tree using BFS are: 1
更新于：2021年1月29日
1K+ 次浏览
广告