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

问题描述 投票：15回答：7

我有一棵树作为广度优先搜索的输入，我想知道算法进展到哪个级别？

# 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')

它将树作为输入图，我想要的是，在每次迭代时它应该打印出正在处理的当前级别。

algorithm data-structures graph graph-algorithm
7个回答
31
投票

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

除了用于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);
     }
4
投票

维护一个队列，在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的答案帖子。

3
投票

试试看这篇文章吧。它使用变量currentDepth跟踪深度

https://stackoverflow.com/a/16923440/3114945

对于您的实现，跟踪最左侧节点和深度变量。每当从队列中弹出最左边的节点时，您就知道你达到了一个新的水平，并且你增加了深度。

所以，你的根是0级的leftMostNode。然后最左边的孩子是leftMostNode。一旦你点击它，它就变成了1级。这个节点的最左边的孩子是下一个leftMostNode，依此类推。

3
投票

如果您的树完全平衡（即每个节点具有相同数量的子节点），实际上这里有一个简单，优雅的解决方案，具有O（1）时间复杂度和O（1）空间复杂度。我发现这个有用的主要用例是遍历二叉树，尽管它可以很容易地适应其他树的大小。

这里要实现的关键是二叉树的每个级别包含与前一级别相比的节点数量的两倍。这允许我们在给定树的深度的情况下计算任何树中的节点总数。例如，请考虑以下树：

enter image description here

该树的总节点深度为3和7。我们不需要计算节点数来解决这个问题。我们可以在O（1）时间内用公式计算：2 ^ d - 1 = N，其中d是深度，N是节点的总数。 （在三元树中，这是3 ^ d - 1 = N，并且在树中，每个节点具有K个子节点，这是K ^ d - 1 = N）。所以在这种情况下，2 ^ 3 - 1 = 7。

为了在进行广度优先搜索时跟踪深度，我们只需要反转此计算。鉴于以上公式允许我们在给定N的情况下求解d，我们实际上想要给d解决N。例如，假设我们正在评估第5个节点。为了确定第5个节点的深度，我们采用以下等式：2 ^ d - 1 = 5，然后简单地求解d，这是基本代数：

enter image description here

如果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);

哪个印刷品：

    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
            )

    )
1
投票

使用此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))
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--) {
        Node temp = queue.poll();
        if (temp.right != null) queue.add(temp.right);
        if (temp.left != null) queue.add(temp.left);
    }    
    level++;
}
0
投票

在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 c:children)
   {
      depthMap.add(c,depthMap.get(parent)+1);//parent's depth + 1

   }

}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.