代码之家 › 专栏 › 技术社区 › Bala Ji

以下BFS的实施效率如何?

breadth-first-search graph-theory data-structures java

Bala Ji · 技术社区 · 1 年前

我正在努力学习BFS,并试图自己分析BFS的时间复杂性。但我无法理解它。下面是我对Graph数据结构和BFS算法的实现。在我的实现中,这里的时间复杂度真的是O(顶点+边)吗。如果没有,我在这里错过了什么效率时间复杂性。

public class Graph {

    private final Map<Vertex, List<Vertex>> nodes;

    public Graph() {
        this.nodes = new HashMap<>();
    }

    public void addEdge(Vertex source, Vertex target) {
        List<Vertex> neighbours = getEdges(source);
        if(!neighbours.contains(target))
            neighbours.add(target);
        this.nodes.put(source, neighbours);
    }

    public List<Vertex> getEdges(Vertex source) {
        return this.nodes.getOrDefault(source, new LinkedList<>());
    }
}

public class BreadthFirstSearch {

    private final Graph graph;
    private final Queue<Vertex> queue;
    private final Set<Vertex> visited;

    public BreadthFirstSearch(Graph graph) {
        this.graph = graph;
        this.queue = new LinkedList<>();
        this.visited = new HashSet<>();
    }

    public void doBFS() {
        this.graph.getNodes().forEach((key, value) -> {
            this.queue.add(key);
            this.queue.addAll(value);
            while(!this.queue.isEmpty()) {
                Vertex vertex = this.queue.poll();
                if(this.visited.contains(vertex)) {
                    continue;
                }
                System.out.print(vertex + " -> ");
                visited.add(vertex);
            }
        });
    }
}

0 回复 | 直到 1 年前

Kevin 1 年前

BFS的时间复杂度为O(V+E)。但是,我对你的代码有一些不理解的地方。在你的 BreadthFirstSearch#doBFS ,您可以添加节点以及该节点可以访问的所有节点。您不应该在BFS中循环每个节点;您只需将第一个节点添加到队列中,并在队列不为空时处理该节点。

public void doBFS(Vertex start) {
    queue.add(start);
    while (!queue.isEmpty()) {
        Vertex current = queue.poll();
        System.out.println("vertex " + current + " visited");
        for (Vertex target : graph.getNodes().getOrDefault(current, List.of())) {
            if (!this.visited.contains(target)) {
                queue.add(target);
            }
        }
    }
}

MT0 1 年前

您尚未实现BFS搜索,因为您不会在到达顶点时迭代地将其添加到队列中——您只会在每次外循环时添加顶点及其紧邻的邻居,这不是BFS。

在Java中:

HashMap.foreach 时间复杂度为 O(buckets + n) -对于固定数量的哈希桶,这是有效的 O(n) .
Collection.add 时间复杂度为 O(1) .
Collection.addAll 时间复杂度为 O(n) .
LinkedList.poll 时间复杂度为 O(1) .
Collection.isEmpty 时间复杂度为 O(1) .
HashSet.contains 最坏情况下的时间复杂度为 O(log(n)) (或 O(n) 如果您使用的是Java 7或更低版本)。假设你的对象哈希分布均匀,项目的数量不比所使用的桶的数量大几个数量级 HashSet 则可以认为平均时间复杂度为 O(1) .

因此,代码的每一行都有时间复杂度:

this.graph.getNodes().forEach((key, value) -> {    // O(|V|)
  this.queue.add(key);                             //   O(1)
  this.queue.addAll(value);                        //   O(|vertex.adjacent|)
  while(!this.queue.isEmpty()) {                   //   O(1)
    Vertex vertex = this.queue.poll();             //     O(1)
    if(this.visited.contains(vertex)) {            //     O(log(|V|)) worst-case
      continue;                                    //       O(1)
    }                                              //
    System.out.print(vertex + " -> ");             //     O(1)
    visited.add(vertex);                           //     O(1)
  }                                                //
});                                                //

在这种情况下,使用 addAll 实际上这不是问题,因为对于每个顶点,您都在添加每个相邻的顶点,这相当于在单个方向上迭代边。所以,在整个外环上聚合,你要在每个方向上添加每条边的相邻顶点,所以这是 O(2E) ,或者简单地说 O(E) .

你遇到的问题是,检查顶点是否被访问是 O(log(n)) 最坏情况下的时间复杂度,每次您想将每个顶点添加到队列中时,都会对其执行此操作。由于您检查了每条边的每个相邻顶点,因此在整个过程中,这是 O(E.log(V)) 最坏情况下的时间复杂度(以及 O(E) 假设前面提到的前提条件成立)。

你的整个算法是 O(V + E.log(V)) 最坏情况下的时间复杂度(或 O(V + E.V) 如果您使用的是Java 7或更早版本,则最坏情况下的时间复杂度)以及 O(V + E) 最佳情况/平均时间复杂度(再次假设满足前面的先决条件)。

要解决最坏情况下的时间复杂性问题:

你可以添加一个 visited 旗到 Vertex 对象并在对象上设置标志,或者,如果您的每个顶点都有一个唯一的顺序数字索引(即它们被编号 0 .. |V|-1 ),您可以在 BreadthFirstSearch 对应于每个顶点的对象,并更新数组中的标志。无论哪种方式,您都可以在中更新标志 O(1) 时间。
您可以停止使用 HashMap 存储邻接列表,并将列表作为每个顶点的属性进行存储。

类似于:

public class BreadthFirstSearch {

    private final Graph graph;
    private final Queue<Vertex> queue;
    private final boolean[] visited;

    public BreadthFirstSearch(Graph graph) {
        this.graph = graph;
        this.queue = new LinkedList<>();
        this.visited = new boolean[graph.nodes.size()];
    }

    private void enqueue(final Vertex vertex)
    {
        int index = vertex.index;
        if (!this.visited[index])
        {
            this.queue.add(vertex);
        }
    }

    public void doBFS() {
        this.graph.getNodes().forEach((key, value) -> {
            this.enqueue(key);
            while(!this.queue.isEmpty()) {
                final Vertex vertex = this.queue.poll();
                System.out.print(vertex + " -> ");
                LinkedList<Vertex> neighbours = vertex.getAdjacent();
                for (final Vertex adjacent: neighbours)
                {
                    this.enqueue(adjacent);
                }
            }
        });
    }
}

这假设你可以写一个 vertex.getAdjacent 方法具有 O(1) 最坏情况下的时间复杂性。使用您当前的实现 哈希图 要存储关系,这不太可能,因为 HashMap.get 有 O(log(n) 最坏情况下的时间复杂性。相反,您可能需要将存储相邻边视为每个边上的属性 顶点 实例而不是 哈希图 在图表上。