Topic 3: Fundamentals of Algorithms

Question 1

What are the two types of graph traversal?

Answer 1

Breadth first
Depth first

Question 2

What is the pseudocode to carry out a depth first traversal?

Answer 2

SUB dfs(graph, currentVertex, visited)
append currentVertex to list of visited nodes
FOR vertex in graph[currentVertex]
IF vertex NOT IN visited then
dfs(graph, vertex, visited)
ENDIF
ENDFOR
END SUB

Question 3

What ADT does a depth first traversal use?

Answer 3

Stack

Question 4

What ADT does a breadth first traversal use?

Answer 4

Queue