✏️ 纠错
第 184 题 / 共 201 题
8. 对一个包含V个顶点、E条边的图，执行广度优先搜索，其最优时间复杂度是（）。
你真棒！
📝 题目解析
答案：A
知识点：广度优先搜索（BFS）的时间复杂度
解析：BFS至少需访问所有顶点（O(V)）和所有边（O(E)），总时间复杂度为O(V+E)，这是复杂度的下界，该复杂度在使用邻接表存储时可以达到，因此是最优复杂度。
广度优先搜索（BFS）的时间复杂度取决于存储结构：
- 邻接表存储时，需遍历所有顶点（O(V)）和所有边（O(E)），总复杂度为O(V+E)，这是最优情况。
- 邻接矩阵存储时，复杂度为O(V^2)，非最优。
因此选A。
知识点：广度优先搜索（BFS）的时间复杂度
解析：BFS至少需访问所有顶点（O(V)）和所有边（O(E)），总时间复杂度为O(V+E)，这是复杂度的下界，该复杂度在使用邻接表存储时可以达到，因此是最优复杂度。
广度优先搜索（BFS）的时间复杂度取决于存储结构：
- 邻接表存储时，需遍历所有顶点（O(V)）和所有边（O(E)），总复杂度为O(V+E)，这是最优情况。
- 邻接矩阵存储时，复杂度为O(V^2)，非最优。
因此选A。