请教：下述BFS实现的时间复杂度是否为O(Vertex+Edges)？

你的BFS实现不是标准的广度优先搜索，它的时间复杂度也达不到O(V+E)，问题出在代码逻辑和数据结构选择上，下面具体拆解：

一、核心问题点 #

• 你在doBFS里的遍历逻辑完全偏离BFS的层级探索核心：直接把每个节点和它的所有邻居一次性塞进队列，然后清空队列处理，既没有逐层遍历的过程，还会导致大量重复入队操作。
• Graph类的addEdge方法用LinkedList.contains()判断边是否存在，这个操作是O(n)时间复杂度（n为当前节点的邻居数），会额外增加建图的开销。

二、当前实现的时间复杂度 #

假设图中有V个顶点、E条边：

1. 建图阶段：每次addEdge的contains操作最坏是O(V)（比如每次都要遍历整个邻居列表），总开销可能达到O(E*V)，远高于标准建图的O(E)。
2. BFS阶段：虽然每个顶点只会被实际处理一次（靠visited过滤），但大量重复入队的操作会让队列总操作次数变成O(V+E)的数倍，而且这个逻辑根本不是BFS，复杂度分析没有实际意义。

三、标准BFS为什么是O(V+E) #

标准BFS的逻辑是：从起点入队，每次出队一个顶点，遍历它的所有未访问邻居并入队，直到队列为空（处理连通分量）。在这个过程中：

• 每个顶点只会入队、出队一次，顶点相关操作总开销是O(V)。
• 每条边只会被遍历一次（每个顶点的邻居只会被处理一次），边相关操作总开销是O(E)。
• 所有操作的常数时间累加后，总复杂度就是O(V+E)。

四、代码修正方案 #

1. 优化Graph类（解决建图效率问题） #

把邻居列表换成HashSet，让contains和添加操作变成O(1)：

public class Graph {
    private final Map<Vertex, Set<Vertex>> nodes;

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

    public void addEdge(Vertex source, Vertex target) {
        Set<Vertex> neighbours = nodes.getOrDefault(source, new HashSet<>());
        neighbours.add(target);
        nodes.put(source, neighbours);
        // 如果是无向图，需要添加反向边：
        // neighbours = nodes.getOrDefault(target, new HashSet<>());
        // neighbours.add(source);
        // nodes.put(target, neighbours);
    }

    public Set<Vertex> getEdges(Vertex source) {
        return nodes.getOrDefault(source, new HashSet<>());
    }

    // 补充原代码缺失的getNodes方法
    public Set<Vertex> getNodes() {
        return nodes.keySet();
    }
}

2. 修正为标准BFS逻辑 #

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<>();
    }

    // 从指定起点开始BFS
    public void doBFS(Vertex start) {
        if (visited.contains(start)) return;
        queue.add(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            Vertex current = queue.poll();
            System.out.print(current + " -> ");
            // 遍历当前节点的所有邻居
            for (Vertex neighbour : graph.getEdges(current)) {
                if (!visited.contains(neighbour)) {
                    visited.add(neighbour);
                    queue.add(neighbour);
                }
            }
        }
    }

    // 处理非连通图，遍历所有连通分量
    public void doFullBFS() {
        for (Vertex vertex : graph.getNodes()) {
            doBFS(vertex);
        }
    }
}

五、总结 #

修正后的代码既符合标准BFS逻辑，又通过HashSet优化了建图效率，此时时间复杂度才是O(V+E)——每个顶点处理一次，每条边遍历一次，所有操作的常数时间累加后为线性复杂度。

内容的提问来源于stack exchange，提问作者Bala Ji