求bfs时每一层的节点数

Question

你得到了一棵由 N 个节点组成的树。树是由 N 个节点和 N−1 条边组成的全连接图。这棵树中的节点从 1 到 N 进行索引。将索引为 1 的节点视为这棵树的根节点。根节点位于树中的第一层。您将获得树和一个整数 x 。您需要找出位于 x 层的节点数。

输入格式

第一行由一个整数 N 组成，表示树中的节点数。接下来的 n-1 行中的每一行都由 2 个整数 a 和 b 组成，表示节点 a 和节点 b 之间的无向边。下一行包含一个整数 x.

输出格式

您需要打印单个整数，表示第 x 层的节点数。

下面是我写的代码片段，它不正确。请帮我找出错误。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

public class LevelNodes {
    public static ArrayList[] adj;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        boolean[] visites = new boolean[N];
        ArrayList[] adj = new ArrayList[N];
        for(int j=0;j<N;j++){
            adj[j] = new ArrayList();
        }
        for(int i = 0;i < (N-1) ;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            adj[a-1].add(b);
            adj[b-1].add(a);
        }
        int level = sc.nextInt();
        int counter = 0;
        LinkedList list = new LinkedList();
        list.add(1);
        counter++;
        while(!list.isEmpty()){
            int n = (Integer) list.poll();
            for(int x = 0; x< adj[n-1].size();x++){
                list.add(adj[n-1].get(x));
            }
            counter++;
            if(counter == level){
                System.out.println(list.size());
                break;
            }

        }
    }

}

Answer 1

您的代码中存在一些问题：

第一个问题是您的代码可能不会终止。这是因为您将边 u->v 和 v->u 添加到邻接表中。因此，每当您从列表中轮询 u 并添加其邻居时，您都会将 v 添加到列表中。同样，无论何时轮询 v 并添加其邻居，您都会将 u 添加回列表。您需要维护一个布尔数组 visited 并在您将 u 添加到列表时设置 visited[u]=true 。这样您就可以只将未访问的节点添加到扫描列表中。

另一个主要问题是在 while 循环中。每当您访问新节点时，您都会增加级别计数器变量 counter++;。考虑下面的树，假设我们需要找到第 2 层（最后一层）的节点数。

最初您的列表包含 1 和 counter=1。在第一次迭代中，您从列表中轮询 1 并添加其邻居：2 和 3。在此阶段，counter=2。在接下来的两次迭代中，您将从列表中删除 2 然后 3，添加它们的邻居，并每次递增 counter。所以当你到达第二级时，counter 将等于 4。If 语句将永远不会被执行。

要解决此问题，您必须递增 counter，前提是您已完成当前级别的所有节点处理。一种简单（未经测试）的方法是使用第二个临时列表来保存当前级别所有节点的邻居。然后，只要原始列表为空，您就知道您已经处理了当前级别的所有节点。在这里，您递增 counter 并将所有节点从临时列表移至主列表。

while(!list.isEmpty()){
    int n = (Integer) list.poll();
    for(int x = 0; x< adj[n-1].size();x++){
        tmpList.add(adj[n-1].get(x));
    }

    if(list.isEmpty()) {
        if(counter == level){
            System.out.println(tmpList.size());
            break;
        }

        list.addAll(tmpList);
        tmpList.clear();
        counter++;
    }
}

求bfs时每一层的节点数

Finding the number of nodes at each level during bfs

java

algorithm

graph

tree

breadth-first-search