GO Classes DPP | PYTHON & DSA |GRAPH

Answer 1

Answer: B, C, and D

 

Explanation

• A. Finding if a specific edge $\mathbf{(u, v)}$ exists takes $\mathbf{O(1)}$ time in the worst case.
  • This is False. In an adjacency list implemented with a standard list for neighbors, finding $v$ in $u$'s neighbor list requires a linear scan, which takes $O(\text{out-degree}(u))$ time in the worst case, not $O(1)$.
• B. Computing the out-degree of a vertex $\mathbf{u}$ takes $\mathbf{O(1)}$ time if using Python's $\mathbf{len(adj[u])}$.
  • This is True. Accessing adj[u] in a Python dictionary is $O(1)$ on average, and getting the length of a list using len() is also an $O(1)$ operation.
• C. Computing the in-degree of a vertex $\mathbf{u}$ takes $\mathbf{O(n + m)}$ time in the worst case.
  • This is True. To find the in-degree of a specific vertex $u$, one must iterate through all adjacency lists of all vertices to count how many times $u$ appears as a neighbor. This involves checking every edge in the graph, resulting in an $O(n+m)$ time complexity.
• D. Performing a Breadth-First Search (BFS) starting from a source vertex $\mathbf{s}$ takes $\mathbf{O(n + m)}$ time.
  • This is True. The standard time complexity for a BFS on an adjacency list representation is $O(V + E)$, which corresponds to $O(n+m)$ in this case, as every vertex and every edge is visited once.