lesson 21/05/20 Graphs traversal algorithms

Question 1

What are the 2 approaches of searching a graph

Answer 1

Depth-first and breadth-first

Question 2

does Depth-first use a stack or queue

Answer 2

Uses a stack

Question 3

does Breadth-first use a stack or queue

Answer 3

Uses a queue

Question 4

describe how a depth-first approach works

Answer 4

• start at the root of graph
• follow one branch as far as you can go
• backtrack until you find a new route
• repeat until you go through every root
• pop everything off

Question 5

describe how a breadth-first approach works

Answer 5

• start at the root of graph
• scan each branch the front of queue has
• pop front when it has no new routes
• repeat until every route has been scanned
• pop everything off

Question 6

examples of a real life depth-first approach

Answer 6

GPS Navigation systems, computer Networks (peer-to-peer)