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