Graph bug hunt

Questions 1 to 5 of 8

1. 1. The DFS below is run on a graph where vertex 0 links to 1 and vertex 1 links back to 0. It raises RecursionError. Which change lets the DFS finish its walk? ``python def dfs(graph, node, calls): calls[0] += 1 for nxt in graph[node]: dfs(graph, nxt, calls) ``

   Wrap the call in a try block that catches RecursionErrorReplace calls[0] += 1 with a loop that counts the neighboursAdd a visited set argument, and at the top of the function return if node is in it, otherwise add node to itReverse the loop so it visits the last neighbour first
2. 2. A set visited already contains 3. What does visited.add(3) return?

   True, and the set now holds two copies of 3NoneFalse, and the set is unchangedIt raises a KeyError
3. 3. What does this code print? ``python from collections import deque def reachable_bfs(graph, start): seen = {start} order = [] queue = deque([start]) while queue: node = queue.popleft() order.append(node) for nxt in graph[node]: if nxt not in seen: seen.add(nxt) queue.append(nxt) return order print(reachable_bfs([[2, 1], [3], [], []], 0)) ``

   [0, 1, 2, 3][0, 1, 3, 2][0, 2, 3, 1][0, 2, 1, 3]
4. 4. This BFS should visit each vertex once. It runs on a graph where vertices 1 and 2 both link to 3, so the graph is [[1, 2], [3], [3], []] and the start is 0. What is wrong with it? ``python seen = {start} queue = deque([start]) while queue: node = queue.popleft() for nxt in graph[node]: if nxt not in seen: queue.append(nxt) seen.add(node) ``

   It never calls popleft, so the queue is never emptiedIt marks a vertex as seen when it is popped, so a vertex can be queued more than once before thatIt uses in instead of add, so the set is never filled and the loop raises an exceptionIt starts from the wrong vertex, so the start vertex is never visited
5. 5. A task graph has the edge (0, 1), which means task 0 must finish before task 1 starts. The code below builds the graph with n = 2 and edges = [(0, 1)]. ``python def build_graph(n, edges): graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) graph[b].append(a) return graph `` What is the effect?

   The build raises an IndexError on the first edgeTasks 0 and 1 are no longer connected by any pathStarting from task 1 now reaches task 0, which the task rules do not allowStarting from task 1 reaches only task 1, as before