Dayup
目录

广度优先搜索

Dayup 约 6 分钟 技术 算法
目录

一、概述

广度优先搜索是一种遍历算法，可以用于遍历树或者图。广度优先搜索(BFS)在遍历时会先遍历完同一层次或者说邻居节点，而不是像广度优先搜索一搜到底。
接下来，我们来看看这种算法在树和图的遍历中是怎么实现的。

二、树结构中的广度优先搜索

树的 BFS 算法背后的想法是维护一个节点队列，以确保遍历的顺序。在算法开始时，队列只包含根节点。只要队列仍然包含一个或多个节点，我们就会重复这些步骤：时间复杂度O(n)

  • 从队列中弹出一个节点
  • 如果该节点是我们正在搜索的节点，则搜索结束
  • 否则，将此节点的子节点添加到队列的末尾，然后重复以上步骤
  • 树结构中没有循环可以保证程序必定会终止。
public static <T> Optional<Tree<T>> search(T value, Tree<T> root) {
    Queue<Tree<T>> queue = new ArrayDeque<>();
    queue.add(root);

    while(!queue.isEmpty()) {
        Tree<T> currentNode = queue.remove();               // 从队列中弹出一个节点
        if (currentNode.getValue().equals(value)) {
            return Optional.of(currentNode);                // 如果该节点是我们正在搜索的节点，则搜索结束
        } else {
            queue.addAll(currentNode.getChildren());        // 否则，将此节点的子节点添加到队列的末尾
        }
    }
    return Optional.empty();                    // 没有找到
}

public class Tree<T> {                          // 树结构
    private T value;
    private List<Tree<T>> children;

    private Tree(T value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    public static <T> Tree<T> of(T value) {
        return new Tree<>(value);
    }

    public Tree<T> addChild(T value) {
        Tree<T> newChild = new Tree<>(value);
        children.add(newChild);
        return newChild;
    }
}

三、图结构中的广度优先搜索

图和树的主要区别是，图包含环。如果我们简单地将前面的算法应用于一个有循环的图，它会一直循环。为了避免在环内循环搜索，需要在遍历节点后保留访问过的节点的集合，确保我们不会访问它们两次。

  • 从队列中弹出一个节点
  • 检查节点是否已经存在被访问过节点集合中，如果是则跳过它
  • 如果该节点是我们正在搜索的节点，则搜索结束
  • 否则，将其添加到已被访问节点集合中
  • 将此节点的邻居节点添加到队列中，然后重复以上步骤
public static <T> Optional<Node<T>> search(T value, Node<T> start) {
    Queue<Node<T>> queue = new ArrayDeque<>();
    queue.add(start);

    Node<T> currentNode;
    Set<Node<T>> alreadyVisited = new HashSet<>();

    while (!queue.isEmpty()) {
        currentNode = queue.remove();                                   // 从队列中弹出一个节点
        LOGGER.debug("Visited node with value: {}", currentNode.getValue());

        if (currentNode.getValue().equals(value)) {                     // 如果该节点是我们正在搜索的节点，则搜索结束
            return Optional.of(currentNode);
        } else {
            alreadyVisited.add(currentNode);                            // 将其添加到已被访问节点集合中
            queue.addAll(currentNode.getNeighbors());                   // 将此节点的邻居节点添加到队列中
            queue.removeAll(alreadyVisited);                            // 检查节点是否已经存在被访问过节点集合中，如果是则跳过它,确保不会陷入死循环
        }
    }

    return Optional.empty();
}


public class Node<T> {
    private T value;
    private Set<Node<T>> neighbors;

    public Node(T value) {
        this.value = value;
        this.neighbors = new HashSet<>();
    }

    public void connect(Node<T> node) {
        if (this == node) throw new IllegalArgumentException("Can't connect node to itself");
        this.neighbors.add(node);
        node.neighbors.add(this);
    }
}
  • 让我们考虑节点的数量n和图的连接数c。在最坏的情况下(没有找到节点)，我们可能会使用addAll()和 removeAll()方法来添加和删除节点，直到达到连接数，所以这些操作是O(c)的复杂度。假设c > n，那整个算法的复杂度将为 O(c);否则，是 O(n)。这通常被称为 O(n + c)，可以解释为复杂性取决于n和c之间的最大数。

四、小结

在本文中，我们讨论了树和图数据结构的广度优先搜索。

参考：

  1. https://www.baeldung.com/java-breadth-first-search —by baeldung
← 返回技术