4.3.1 Graph Traversal

Question 1

What is an algorithm?

Answer 1

A set of instructions which completes a task within a finite time and terminates upon completion.

Question 2

What is Graph Traversal?

Answer 2

The process of visiting each vertex in a graph.

Question 3

Name two types of graph traversal.

Answer 3

Depth-first Search and Breadth-first Search

Question 4

Which traversal is best for navigating a maze?

Answer 4

Depth-first search

Question 5

What is breadth-first search useful for?

Answer 5

Shortest path on an unweighted graph

Question 6

What ADT is used for a breadth-first traversal?

Answer 6

Queue

Question 7

What ADT is used for a depth-first search?

Answer 7

Stack

Question 8

What type of graphs can be traversed?

Answer 8

Connected graphs

Question 9

Can a tree undergo depth-first traversal?

Answer 9

• Yes
• But it might be more appropriate to use a tree traversal in such a situation

Question 10

Can a graph traversal start from any node?

Answer 10

• Yes
• Since it is stored in a way that allows to see which nodes have a vertex between them

Question 11

In what order would this graph be traversed in a breadth-first search? Start from node A.

• A → B,C
• B → C,D
• C → A,B
• D → B,E

Answer 11

A→B→C→D→E

Question 12

In what order would this graph be traversed in a depth-first search? Start from node A.

• A → B,C
• B → C,D
• C → A,B
• D → B,E

Answer 12

A → B → D → E → C

Goes through one pathway completely before exploring the other.