03 Fundamentals of Algorithms

Question 1

What is depth-first graph traversal?

Answer 1

Going as far down a path as possible before backtracking and going down next path e.g. used to navigate a maze

Uses a list to hold nodes visited and a stack to keep track of the last node visited

Question 2

What is breadth-first graph traversal?

Answer 2

starts searching at a designated start node and searches through all the adjacent nodes (neighbours) before moving on e.g. commonly used to find the path containing the least number of nodes between two points in an unweighted graph

Uses a list to hold nodes visited and a queue is used to keep track of the next nodes to visit

Question 3

What is the time complexity for DFS and BFS

Answer 3

O(n^2)