如何跟踪广度优先搜索的深度？
How to keep track of depth in breadth first search?
我有一个树作为广度优先搜索的输入，我想知道随着算法的进展，它处于哪个级别？
# 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')
它以树作为输入图，我想要的是，在每次迭代时它应该打印出正在处理的当前级别。
试着看看这个 post。它使用变量 currentDepth
跟踪深度
对于您的实施，请跟踪最左侧的节点和深度变量。每当最左边的节点从队列中弹出时，您就知道您达到了一个新的水平并增加了深度。
所以，你的根是第 0 级的 leftMostNode。那么最左边的 child 就是 leftMostNode。一打就变成1级了，这个节点最左边child是下一个leftMostNode，以此类推。
维护一个队列，存储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) 额外 space 你可能需要@stolen_leaves.
的答案 post
您不需要使用额外的队列或进行任何复杂的计算来实现您想要做的事情。这个想法很简单。
除了用于 BFS 的队列外，这不会使用任何额外的 space。
我要使用的想法是在每个级别的末尾添加 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);
}
如果您的树是完美平衡的（即每个节点都有相同数量的子节点），这里实际上有一个简单、优雅的解决方案，时间复杂度为 O(1)，复杂度为 O(1) space。我发现这有帮助的主要用例是遍历二叉树，尽管它很容易适应 table 到其他树大小。
这里要认识到的关键是二叉树的每一层包含的节点数量是上一层的两倍。这允许我们在给定树的深度的情况下计算任何树中的节点总数。例如，考虑以下树：
这棵树的深度为 3，总共有 7 个节点。我们不需要计算节点的数量来解决这个问题。我们可以使用以下公式在 O(1) 时间内进行计算：2^d - 1 = N，其中 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 结果不是整数，则四舍五入（一行中的最后一个节点始终是整数）。考虑到这一点，我提出了以下算法来在广度优先遍历期间识别二叉树中任何给定节点的深度：
- 让变量
visited 等于 0。
- 每访问一个节点，
visited加1。
- 每次
visited递增，计算节点的深度为depth = round_up(log2(visited + 1))
您还可以使用散列 table 将每个节点映射到其深度级别，尽管这确实会将 space 复杂度增加到 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);
打印：
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
)
)
使用此 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))
在Java中会是这样的。
这个想法是看 parent 来决定深度。
//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
}
}
}
实际上，我们不需要额外的队列来存储当前深度的信息，也不需要添加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++;
}
我在python写了一个简单易读的代码。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def dfs(self, root):
assert root is not None
queue = [root]
level = 0
while queue:
print(level, [n.val for n in queue if n is not None])
mark = len(queue)
for i in range(mark):
n = queue[i]
if n.left is not None:
queue.append(n.left)
if n.right is not None:
queue.append(n.right)
queue = queue[mark:]
level += 1
用法，
# [3,9,20,null,null,15,7]
n3 = TreeNode(3)
n9 = TreeNode(9)
n20 = TreeNode(20)
n15 = TreeNode(15)
n7 = TreeNode(7)
n3.left = n9
n3.right = n20
n20.left = n15
n20.right = n7
DFS().dfs(n3)
结果
0 [3]
1 [9, 20]
2 [15, 7]
在探索图形时，使用字典来跟踪每个节点的级别（距起点的距离）。
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
设置一个变量cnt并将其初始化为队列的大小cnt=queue.size()，现在每次弹出时递减cnt。当 cnt 变为 0 时，增加 BFS 的深度，然后再次设置 cnt=queue.size()。
到目前为止我还没有看到这个方法，所以这里有一个简单的方法：
您可以将关卡“附加”到节点。例如，在树的情况下，使用 queue<pair<TreeNode*,int>> 而不是典型的 queue<TreeNode*>，然后将成对的 {node,level} 推入其中。 root 将被推入为 q.push({root,0})，其子项为 q.push({root->left,1})、q.push({root->right,1}) 等等...
我们不需要修改输入，追加 null 甚至（渐近地讲）使用任何额外的 space 只是为了跟踪级别。
我有一个树作为广度优先搜索的输入，我想知道随着算法的进展，它处于哪个级别？
# 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')
它以树作为输入图，我想要的是，在每次迭代时它应该打印出正在处理的当前级别。
试着看看这个 post。它使用变量 currentDepth
对于您的实施，请跟踪最左侧的节点和深度变量。每当最左边的节点从队列中弹出时，您就知道您达到了一个新的水平并增加了深度。
所以，你的根是第 0 级的 leftMostNode。那么最左边的 child 就是 leftMostNode。一打就变成1级了，这个节点最左边child是下一个leftMostNode，以此类推。
维护一个队列，存储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) 额外 space 你可能需要@stolen_leaves.
的答案 post您不需要使用额外的队列或进行任何复杂的计算来实现您想要做的事情。这个想法很简单。
除了用于 BFS 的队列外，这不会使用任何额外的 space。
我要使用的想法是在每个级别的末尾添加 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);
}
如果您的树是完美平衡的（即每个节点都有相同数量的子节点），这里实际上有一个简单、优雅的解决方案，时间复杂度为 O(1)，复杂度为 O(1) space。我发现这有帮助的主要用例是遍历二叉树，尽管它很容易适应 table 到其他树大小。
这里要认识到的关键是二叉树的每一层包含的节点数量是上一层的两倍。这允许我们在给定树的深度的情况下计算任何树中的节点总数。例如，考虑以下树：
这棵树的深度为 3，总共有 7 个节点。我们不需要计算节点的数量来解决这个问题。我们可以使用以下公式在 O(1) 时间内进行计算：2^d - 1 = N，其中 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 结果不是整数，则四舍五入（一行中的最后一个节点始终是整数）。考虑到这一点，我提出了以下算法来在广度优先遍历期间识别二叉树中任何给定节点的深度：
- 让变量
visited等于 0。 - 每访问一个节点，
visited加1。 - 每次
visited递增，计算节点的深度为depth = round_up(log2(visited + 1))
您还可以使用散列 table 将每个节点映射到其深度级别，尽管这确实会将 space 复杂度增加到 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);
打印：
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
)
)
使用此 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))
在Java中会是这样的。 这个想法是看 parent 来决定深度。
//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
}
}
}
实际上，我们不需要额外的队列来存储当前深度的信息，也不需要添加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++;
}
我在python写了一个简单易读的代码。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def dfs(self, root):
assert root is not None
queue = [root]
level = 0
while queue:
print(level, [n.val for n in queue if n is not None])
mark = len(queue)
for i in range(mark):
n = queue[i]
if n.left is not None:
queue.append(n.left)
if n.right is not None:
queue.append(n.right)
queue = queue[mark:]
level += 1
用法，
# [3,9,20,null,null,15,7]
n3 = TreeNode(3)
n9 = TreeNode(9)
n20 = TreeNode(20)
n15 = TreeNode(15)
n7 = TreeNode(7)
n3.left = n9
n3.right = n20
n20.left = n15
n20.right = n7
DFS().dfs(n3)
结果
0 [3]
1 [9, 20]
2 [15, 7]
在探索图形时，使用字典来跟踪每个节点的级别（距起点的距离）。
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
设置一个变量cnt并将其初始化为队列的大小cnt=queue.size()，现在每次弹出时递减cnt。当 cnt 变为 0 时，增加 BFS 的深度，然后再次设置 cnt=queue.size()。
到目前为止我还没有看到这个方法，所以这里有一个简单的方法：
您可以将关卡“附加”到节点。例如，在树的情况下，使用 queue<pair<TreeNode*,int>> 而不是典型的 queue<TreeNode*>，然后将成对的 {node,level} 推入其中。 root 将被推入为 q.push({root,0})，其子项为 q.push({root->left,1})、q.push({root->right,1}) 等等...
我们不需要修改输入，追加 null 甚至（渐近地讲）使用任何额外的 space 只是为了跟踪级别。