我有一个树作为广度优先搜索的输入,我想知道随着算法的进展它在哪个级别?
# 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')
它以树作为输入图,我想要的是,在每次迭代时它应该打印出正在处理的当前级别。
最佳答案
实际上,我们不需要额外的队列来存储当前深度的信息,也不需要添加 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++;
}
关于algorithm - 如何跟踪广度优先搜索的深度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31247634/