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

以下BFS的实施效率如何?

  •  0
  • Bala Ji  · 技术社区  · 3 月前

    我正在努力学习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 回复  |  直到 3 月前
        1
  •  0
  •   Kevin    3 月前

    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);
                }
            }
        }
    }
    
        2
  •  0
  •   MT0    3 月前

    您尚未实现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) 最坏情况下的时间复杂性。相反,您可能需要将存储相邻边视为每个边上的属性 顶点 实例而不是 哈希图 在图表上。