Terms

Question 1

What is Depth-first search (DFS)

Answer 1

The algorithm starts at the root node and explores as far as possible along each branch before backtracking.

procedure DFS(G, v) is
label v as discovered
for all directed edges from v to w that are in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G, w)

Question 2

What is Breadth-first search (BFS)

Answer 2

It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.

1 procedure BFS(G, root) is
2 let Q be a queue
3 label root as explored
4 Q.enqueue(root)
5 while Q is not empty do
6 v := Q.dequeue()
7 if v is the goal then
8 return v
9 for all edges from v to w in G.adjacentEdges(v) do
10 if w is not labeled as explored then
11 label w as explored
12 w.parent := v
13 Q.enqueue(w)