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

With an adjacency matrix representation, each time BFS examines the neighbors of a vertex u it must scan the entire row of the matrix (one entry per vertex) to test adjacency. Therefore:

1. Relevant knowledge points and concepts
- BFS visits each vertex at most once (each vertex is popped from the queue at most once).
- With an adjacency matrix, "for each vertex v adjacent to u" requires scanning all |V| possible v to check the adjacency entry.
- Auxiliary structures used by BFS: dist[1..|V|], pred[1..|V|], and the queue (size ≤ |V|). The adjacency matrix (the input) is excluded from auxiliary-space accounting.

2. Step-by-step reasoning / intermediate steps
- Number of times we pop u from the queue ≤ |V| (each vertex at most once).
- For each popped u we scan all |V| entries in the u-th row of the adjacency matrix to find adjacent vertices. So adjacency checks = O(|V|) per vertex u.
- Total adjacency checks across the whole run = |V| * |V| = |V|^2.
- Each adjacency check is O(1), and each discovered edge causes O(1) work (set dist, pred, push), so total time = Θ(|V|^2).

3. Space calculation (intermediate terms)
- dist array: Θ(|V|)
- pred array: Θ(|V|)
- queue: up to Θ(|V|)
- combined auxiliary space = Θ(|V|) (constant factors omitted).

4. Why the correct answer is correct
- Time Θ(|V|^2) is driven by scanning the full adjacency matrix rows for each vertex independent of the number of edges. Space Θ(|V|) counts only the working arrays/queue used by BFS, not the input matrix.

5. Why other options are incorrect (brief)
- Θ(|V| + |E|) or Θ(|E|) apply when using adjacency lists; with an adjacency matrix you cannot avoid scanning |V| entries per vertex, so those are too small.
- Any Θ(|V| log |V|), Θ(|V|^3), Θ(|E|^2), etc., are either too small or unnecessarily large compared to the precise Θ(|V|^2) time and Θ(|V|) space.

Conclusion: The worst-case time complexity is Θ(|V|^2) and the auxiliary space complexity is Θ(|V|), which matches the correct answers above.

类似问题

A project has a required return of 12.6 percent, an initial cash outflow of $42,100, and cash inflows of $16,500 in Year 1, $11,700 in Year 2, and $10,400 in Year 4. What is the net present value?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单