Recall the algorithm for shortest paths in an unweighted graph. We provide it below, as given in the course notes. [table]
1
2 3
4 5
6 7
8 9
10 11 12 13 | function BFS(G = (V, E), s) dist[1..n] = ∞ pred[1..n] = null queue = Queue() queue.push(s) dist[s] = 0 while queue is not empty do u = queue.pop() for each vertex v adjacent to u do if dist[v] = ∞ then dist[v] = dist[u] + 1 pred[v] = u queue.push(v)
[/table] Analyse this algorithm and provide:Its worst-case time complexity, Its auxiliary space complexity (excluding the input). Assume the graph is stored as an adjacency matrix. Make no assumption on the edge density of the graph.Select one worst-case time complexity and one auxiliary space complexity from the list below. Two correct answers and zero incorrect answers are required to pass this question.

Question

BlackTom AI · Accepted Answer

Scanning each row of the adjacency matrix to find neighbours takes Θ(|V|) time per vertex, so BFS over all vertices costs Θ(|V|^2). Below is a structured explanation.

1) Relevant knowledge points and concepts
- Breadth-first search (BFS) visits each vertex once (queue push/pop at most |V| times).
- With an adjacency matrix, to enumerate neighbours of a vertex u you must inspect its entire row of length |V| (check each possible v for an edge).
- Auxiliary space excludes the input graph storage (the adjacency matrix).

2) Step-by-step reasoning
- Let n = |V|.
- BFS loop: each time we pop a vertex u we execute “for each vertex v adjacent to u” by scanning the row of u in the matrix (n entries).
- In the worst case BFS will pop every vertex once (≤ n pops).
- Therefore the number of adjacency checks = n rows × n entries = n^2 checks.

3) Intermediate calculation steps
- Work for adjacency inspection: n × n = n^2 checks.
- Each check is O(1), so total time = c·n^2 for some constant c.
- Additional work (initializing dist/pred arrays, queue operations) is O(n).
- Combine: total time = Θ(n^2 + n) = Θ(n^2) = Θ(|V|^2).

4) Why the correct answer is correct
- Because adjacency enumeration costs Θ(n) per vertex and BFS visits Θ(n) vertices in worst case, the asymptotic worst-case running time is Θ(|V|^2).

5) Why other options are incorrect (brief)
- Θ(|V| + |E|) (or Θ(|E|)) is the correct bound when the graph is stored as adjacency lists, not as a matrix.
- Bounds like Θ(|V| log |V|), Θ(|V|^3), Θ(|E|^2), etc., do not match the per-vertex row-scan cost of the adjacency-matrix implementation and are therefore incorrect.

6) Conclusion / final confirmation
- Worst-case time complexity: Θ(|V|^2).
- Auxiliary space (excluding the input matrix): arrays dist and pred (Θ(|V|) each) plus the queue (≤ Θ(|V|)) → total Θ(|V|).
These match the provided answers: Θ(|V|^2) time and Θ(|V|) auxiliary space.

类似问题

In a breadth-first search of an undirected graph G, starting at vertex v, which of the following is true when the vertex w is found in level i?

In a breadth-first search of an undirected graph G, starting at vertex v, which of the following is true?

A complete graph is one where every two vertices are connected with an edge. Suppose we run BFS on a complete graph G(V,E) starting from some vertex s in V . What would the BFS layers look like?

Given a graph-G that has |V| vertices and |E| edges, that is:Connected. Directed. Weighted What is the worst case time complexity to run Breadth-First Search (BFS), if G is implemented using adjacency list?

Which of the following is true about BFS traversal (from a given source) of an unweighted, connected and undirected graph?

What data structure is commonly used to implement Breadth-First Search (BFS)?

The below is a search tree, using breadth first search to reach goal Hamera. What is the answer ____.

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单