Graph traversal algorithm

Question 1

2 types of traversing a graph

Answer 1

Breadth first
Depth first

Question 2

What is used in a depth first traversal

Answer 2

A stack to track last node visited
A list to hold names of nodes already met

Question 3

What are the steps of a depth first traversal

Answer 3

Visit the node and add to the visited list

Then push the node onto a stack then go to the next node

Continue until you cannot go any further

Then pop off the stack till you get to a node that has an available next node

Once stack is empty this shows the algorithm has been finished

Question 4

What is used in a breadth first traversal

Answer 4

A queue is used to keep track of the nodes left to visit

Question 5

What are the steps in a breadth first traversal

Answer 5

Append first node to an empty queue

Dequeue the node and add to a visited list

Then check the nodes adjacent and append them to the queue

Then dequeue the node at the start of the queue

Continue until you have an empty queue

Question 6

Difference between depth first traversal and breadth first traversal

Answer 6

Depth-first you go as far down the path you can before backtracking and trying a new path

Breadth-first you explore the neighbouring nodes of the current vertex