如何在广度优先搜索中跟踪深度？

Question

我有一棵树作为广度优先搜索的输入，我想知道算法在进行时处于哪个层级？

# Breadth First Search Implementation
graph = { 
    'A':['B','C','D'],
    'B':['A'],
    'C':['A','E','F'],
    'D':['A','G','H'],
    'E':['C'],
    'F':['C'],
    'G':['D'],
    'H':['D']
    }


def breadth_first_search(graph,source):
    """
    This function is the Implementation of the breadth_first_search program
    """
    # Mark each node as not visited
    mark = {}
    for item in graph.keys():
        mark[item] = 0

    queue, output = [],[]

    # Initialize an empty queue with the source node and mark it as explored
    queue.append(source)
    mark[source] = 1
    output.append(source)

    # while queue is not empty
    while queue:
        # remove the first element of the queue and call it vertex
        vertex = queue[0]
        queue.pop(0)
        # for each edge from the vertex do the following
        for vrtx in graph[vertex]:
            # If the vertex is unexplored
            if mark[vrtx] == 0:
                queue.append(vrtx)  # mark it as explored
                mark[vrtx] = 1      # and append it to the queue
                output.append(vrtx) # fill the output vector
    return output

print breadth_first_search(graph, 'A')

它以树作为输入图形，在每次迭代中，我想要的是打印出当前处理的层级。

- jsonbourne

---

你正在制作自己的BFS（广度优先搜索）实现吗？如果是，那么你只需要使用和维护一个 depthCounter（深度计数器）。或者你正在使用任何现成的算法吗？ - stolen_leaves

我已经添加了代码，没有现成的算法，只是一个常规的广度优先搜索实现。 - jsonbourne

Answer 1

实际上，我们不需要额外的队列来存储当前深度的信息，也不需要添加 null 来告知当前层是否结束。我们只需要知道当前层包含多少个节点，然后就可以处理同一层中的所有节点，在处理完当前层的所有节点之后，将层数增加1即可。

int level = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
    int level_size = queue.size();
    while (level_size-- != 0) {
        Node temp = queue.poll();
        if (temp.right != null) queue.add(temp.right);
        if (temp.left != null) queue.add(temp.left);
    }    
    level++;
}

- KDD

Answer 2

你不需要使用额外的队列或进行任何复杂的计算来实现你想做的事情。这个想法非常简单。

除了用于 BFS 的队列之外，这不会使用任何额外的空间。

我要使用的想法是在每个级别的末尾添加 null。所以你遇到的空值数量+1就是你所在的深度。（当然，在终止后它只是level）。

     int level = 0;
     Queue <Node> queue = new LinkedList<>();
     queue.add(root);
     queue.add(null);
     while(!queue.isEmpty()){
          Node temp = queue.poll();
          if(temp == null){
              level++;
              queue.add(null);
              if(queue.peek() == null) break;// You are encountering two consecutive `nulls` means, you visited all the nodes.
              else continue;
          }
          if(temp.right != null)
              queue.add(temp.right);
          if(temp.left != null)
              queue.add(temp.left);
     }

- Karthik

Answer 3

维护一个队列，存储BFS队列中相应节点的深度。以下是示例代码：

queue bfsQueue, depthQueue;
bfsQueue.push(firstNode);
depthQueue.push(0);
while (!bfsQueue.empty()) {
    f = bfsQueue.front();
    depth = depthQueue.front();
    bfsQueue.pop(), depthQueue.pop();
    for (every node adjacent to f) {
        bfsQueue.push(node), depthQueue.push(depth+1);
    } 
}

这种方法简单而朴素，如果你需要O(1)额外空间的答案，可以参考@stolen_leaves发表的帖子。

- matrixit

Answer 4

请看这篇帖子，它使用变量currentDepth跟踪深度。

链接：https://dev59.com/t2kv5IYBdhLWcg3w6lDj#16923440 对于您的实现，请跟踪最左侧的节点和一个深度变量。每当最左侧的节点从队列中弹出时，您就知道已经到达了新的层级，并且应该增加深度。

因此，您的根是位于第0层的leftMostNode。然后，最左侧的子节点是leftMostNode。一旦到达它，它的层级就变成1。该节点的最左侧子节点是下一个leftMostNode，以此类推。

- stolen_leaves

Answer 5

通过这段Python代码，您可以在队列中遇到新深度的节点后才增加深度，从而维护每个节点相对于根节点的深度。

    queue = deque()
    marked = set()
    marked.add(root)
    queue.append((root,0))

    depth = 0
    while queue:
        r,d = queue.popleft()
        if d > depth: # increase depth only when you encounter the first node in the next depth               
            depth += 1
        for node in edges[r]:
            if node not in marked:
                marked.add(node)
                queue.append((node,depth+1))

- MROB

Answer 6

设置一个变量cnt，并将其初始化为队列的大小cnt=queue.size()，现在每次执行pop操作时都将cnt减1。当cnt减到0时，增加BFS的深度，然后再次将cnt=queue.size()。

- Akram ElectroTech

Answer 7

如果您的树完全平衡（即每个节点具有相同数量的子节点），那么实际上存在一个简单而优雅的解决方案，其时间复杂度为O(1)，空间复杂度为O(1)。我发现这在遍历二叉树时非常有用，尽管它可以轻松地适应其他树大小。

关键在于要意识到二叉树的每一层包含的节点数量恰好是前一层的两倍。这使我们可以计算出任何树的总节点数，给定树的深度。例如，考虑以下树：

这棵树的深度为3，总共有7个节点。不过我们不需要计算节点数来得到这个结果。我们可以使用公式2^d - 1 = N来在O(1)的时间内计算出结果，其中d是深度，N是节点总数。（在三叉树中，公式为3^d - 1 = N，在每个节点有K个子节点的树中，公式为K^d - 1 = N）。因此，在这种情况下，2^3 - 1 = 7。

在进行广度优先搜索时跟踪深度，我们只需要反向运用这个公式即可。虽然上面的公式可以让我们求解给定d时的N，但实际上，我们想要求解给定N时的d。例如，假设我们正在评估第5个节点。为了确定第5个节点所在的深度，我们使用以下方程式：2^d - 1 = 5，然后简单地解出d，这是基本的代数运算。

如果d不是整数，就向上取整（每行的最后一个节点总是整数）。考虑到这一点，我提出以下算法，在广度优先遍历期间识别二叉树中任何给定节点的深度：

1. 将变量visited设置为0。 2. 每次访问一个节点时，将visited加1。 3. 每次增加visited时，计算节点的深度为depth = round_up(log2(visited + 1))

您还可以使用哈希表将每个节点映射到其深度级别，但这会增加空间复杂度为O(n)。这是一个PHP实现该算法的示例：

<?php
$tree = [
    ['A', [1,2]],
    ['B', [3,4]],
    ['C', [5,6]],
    ['D', [7,8]],
    ['E', [9,10]],
    ['F', [11,12]],
    ['G', [13,14]],
    ['H', []],
    ['I', []],
    ['J', []],
    ['K', []],
    ['L', []],
    ['M', []],
    ['N', []],
    ['O', []],
];

function bfs($tree) {
    $queue = new SplQueue();
    $queue->enqueue($tree[0]);
    $visited = 0;
    $depth = 0;
    $result = [];

    while ($queue->count()) {

        $visited++;
        $node = $queue->dequeue();
        $depth = ceil(log($visited+1, 2));
        $result[$depth][] = $node[0];


        if (!empty($node[1])) {
            foreach ($node[1] as $child) {
                $queue->enqueue($tree[$child]);
            }
        }
    }
    print_r($result);
}

bfs($tree);

这句话的英文是：Which prints:

    Array
    (
        [1] => Array
            (
                [0] => A
            )

        [2] => Array
            (
                [0] => B
                [1] => C
            )

        [3] => Array
            (
                [0] => D
                [1] => E
                [2] => F
                [3] => G
            )

        [4] => Array
            (
                [0] => H
                [1] => I
                [2] => J
                [3] => K
                [4] => L
                [5] => M
                [6] => N
                [7] => O
            )

    )

- Matt Korostoff

Answer 8

在Java中，它应该是这样的。思路是查看父级以确定深度。

//Maintain depth for every node based on its parent's depth
Map<Character,Integer> depthMap=new HashMap<>();    

queue.add('A');
depthMap.add('A',0); //this is where you start your search

while(!queue.isEmpty())
{
   Character parent=queue.remove();
   List<Character> children=adjList.get(parent);
   for(Character child :children)
   {
      if (child.isVisited() == false) {
           child.visit(parent);
           depthMap.add(child,depthMap.get(parent)+1);//parent's depth + 1
         }

   }

}

- developer747

---

这将导致无限循环。您需要检查子节点是否已被访问。 对于每个子节点： 如果depthMap中不包含该子节点，则进行以下操作：

1. 将该子节点的深度设定为其父节点的深度加一，并在depthMap中添加该子节点。
2. 将该子节点添加到队列中等待遍历。

- NANCY

Answer 9

使用字典来记录探索图时每个节点的级别（距起点的距离）。

Python示例：

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    levels = {start: 0}
    while queue:
        vertex = queue.popleft()
        for neighbour in graph[vertex]:
            if neighbour in levels:
                continue
            queue.append(neighbour)
            levels[neighbour] = levels[vertex] + 1
    return levels

- Anders Åhsman

Answer 10

我还没有看到这个方法的帖子，所以这里有一个简单的方法：

您可以将级别“附加”到节点上。例如，在树的情况下，而不是典型的queue<TreeNode*>，使用queue<pair<TreeNode*，int>>，然后将{node，level}的对推入其中。 root将被推入为q.push（{root，0}），其子项为q.push（{root->left，1}），q.push（{root->right，1}）等等...

我们不需要修改输入、追加nulls，甚至（从渐近意义上讲）不需要使用任何额外的空间来跟踪层次。

- abhishek_naik