A4.3 Depth-first traversal worksheet

Going deep and backtracking, recursively and with a stack; tracing it and what it is used for.

Questions 5 marks in all

[1 mark]Which data structure does an iterative depth-first traversal use?

AA stack
BA queue
CA priority queue
DA hash table

[1 mark]An undirected graph has the edges A-B, A-C and B-D. Put the vertices in the order a depth-first traversal from A visits them, trying neighbours in alphabetical order.

Number the lines 1 to 4 to put them in the right order.

[1 mark]Which application does AQA's specification give for depth-first search?

ANavigating a maze
BFinding the shortest path in an unweighted graph
CSorting a list of numbers
DSearching a sorted array

[1 mark]What does this program print?

GRAPH = {"P": ["Q", "S"], "Q": ["P", "R"], "R": ["Q", "S"], "S": ["P", "R"]}
visited = []
def dfs(v):
    visited.append(v)
    for n in GRAPH[v]:
        if n not in visited:
            dfs(n)
dfs("P")
print(" ".join(visited))

[1 mark]Why does a depth-first traversal mark vertices as visited?

AWithout the marks it could go round a cycle forever
BTo make it find the shortest path
CTo sort the vertices into order
DBecause a stack cannot hold the same item twice

The task: what can be reached

The graph in GRAPH is undirected and stored as an adjacency list: each vertex's neighbours, in the order to try them. Write a function dfs that traverses the graph depth-first from a start vertex, recursively or with your own stack, and records the order in which the vertices are visited. Try the neighbours in the order the list gives them. Print DFS order: followed by the vertices in the order visited from A, separated by single spaces. Then print not reachable: followed by every vertex that was never visited, in alphabetical order, separated by single spaces.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

GRAPH = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
    "G": ["H"],
    "H": ["G"],
}

visited = []

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/a4-3-depth-first-traversal/
The simulator checks it and tells you when it passes. Nothing to install, no account.

Challenges

Make dfs also count the edges it follows to reach a new vertex. How does the count compare with the number of vertices visited, and why?

Write has_path(start, goal) that stops as soon as goal is visited, and returns True or False.

Reverse every neighbour list. Does the DFS order change? Does the set of vertices reached?

What this lesson is about

Questions 5 marks in all

The task: what can be reached

Challenges