# 01 - Graph Traversal Algorithms

1. Arrays and linked lists are examples of linear data structures. On the other hand, graphs and trees are forms of non-linear data structures.

TRUE

FALSE

2. A graph is a system in which there are potentially ____________ to get from an arbitrary point, A, to another arbitrary point, B
`Useful fact: Many problems in computer science can be thought of in terms of graphs. For example, analyzing networks, mapping routes, scheduling, and finding spanning trees are graph problems`

infinite ways (meaning all graphs cannot be traversed successfully)

multiple ways

zero ways

one best and singular way

3. A graph is normally defined as a pair of sets (V,E). V is a set of arbitrary objects called _______________ and E is a set of pairs of vertices, which we call edges or (more rarely) arcs

vertices or nodes,

stacks

lines

queues

4. Two algorithms are generally used for the traversal of a graph: Depth first search (DFS) and _______________________

length-first-search

post-search

In-order search

5. Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a ______

cycle that can only be done once

recursive search function

path that cannot be travsersed easily

boolean visited array

6. Fill in the blanks for this exerpt on solving maze-type problems
```____________________ is a common way that many people naturally use when
solving problems like mazes.

First, we select a path in the maze (for the sake of this example,
let’s choose a path according to some rule we lay out ahead of time)
and we follow it until we hit a dead end or reach the end of the maze.
If a given path doesn’t work, we backtrack and take an alternative
path from a past junction, and try that path.```

Depth-first search

Node-first search

Depth-last search

7. Which of the following definitions is for a Breadth first search algorithm and a Depth first search algorithm?
```Definition #1
==============
The algorithm starts at the root (top) node of a tree and goes as far
as it can down a given branch (path), and then backtracks until it finds
an unexplored path, and then explores it. The algorithm does this until
the entire graph has been explored

Definition #2
==============
It starts at the tree root (or some arbitrary node of a graph, sometimes
referred to as a ‘search key’), and explores all of the neighbor nodes at
the present depth prior to moving on to the nodes at the next depth level```

Definition 1 = Depth First; Definition 2 = Breadth First

Both definitions are for Depth First

Definition 1 = Breadth first; Definition 2 = Depth first

Both definitions are for Breadth first (variations)

8. Analyse the following code (Python). What is likely to go in the line where the ?????????s are?
```def depth_first_search_recursive(graph, start, visited=None):
if visited is None:
visited = set()
for next in graph[start] - visited:
???????????????????????????????????
return visited```

depth_first_search_recursive(graph, next, visited)

depth_first_search_recursive(start, next)

depth_first_search_recursive(next, visited, 1,0)

9. Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following

If {u,v} is not an edge in G then u and v must have the same parent in T

{u,v} must be an edge in G, and v is a descendant of u in T

If {u,v} is not an edge in G then u is a leaf in T

{u,v} must be an edge in G, and u is a descendant of v in T

10. A Depth First Traversal of the following graph is:

2, 0, 1, 3.

0,1,2,3

1,2,0,3

2,1,3,0

11. This is an algorithm for traversing a finite graph. It visits the child vertices before visiting the sibling vertices

Depth Last Search

Depth First Search

12. Analyse the following image and select the option which describes what happens next.

F' is added to the top of the stack and also to the result

D' is added to the top of the stack and also to the result

G' is added to the top of the stack and also to the result

E and B are removed from the stack, and F is added to the top of the stack and result

13. In the following implementation of a DFS, what happens next? Select the option that best describes it
`Note: Assume that we are traversing in alphebetical order. Any order however, would otherwise be acceptable`

G', 'E', 'B' and 'A' come off the stack and 'D' is added to the stack and the result

G' comes off the stack, and 'D' is added to the stack as well as to the result

At this stage, as there are no immediately available nodes, 'H' is added to the stack and to the result

G' and 'E' come off the top of the stack, and 'F' is added to it. 'F' is also added to the result

14. In the implementation of a depth first search, a ______ (often the program's call _____via recursion) is generally used

queue

pointer

stack

iterative function

15. BFS (Breadth first search) visits the neighbor vertices before visiting the child vertices, and a_______ is used in the search process

stack

iterative function

pointer

queue

16. The BFS algorithm is often used to find the _____________________________________

shorst path from the root to the left most child node

shortest path from the root to the right most child node

shortest path from one vertex to another.

longest path from one vertex to another

17. In this Breadth first search, what happens next?

B' is removed from the queue and 'B' becomes the current vertex. 'E' and 'F' or 'F' and 'E' (any order) are added to the queue and the result

B' and 'F' are removed from the queue, and 'E' is added to the queue and to the result.

G' is removed from the queue and 'E' is therefore added to both the queue and the result

G' is removed from the queue and 'F' is added to both the queue and the result

18. Looking at the following graph, and assuming a BFS algorithm implementation with a queue, what is the only possible (from the given options) order of visiting the nodes?

MNOPQR

NQMPOR

QMNPRO

QNPMOR

19. Given two vertices in a graph s and t, which of the two traversals (BFS and DFS) can be used to find if there is path from s to t?

Both BFS and DFS

Neither BFS or DFS

Only DFS

Only BFS

```   public void BFS()
{

Stack s = new Stack();   // I use Stack class in Java's library

for (i = 0; i < visited.length; i++)
visited[i] = false;        // Clear visited[]

s.push(0);                    // Start the "to visit" at node 0

/* ===========================================
Loop as long as there are "active" node
=========================================== */
while( ! s.isEmpty() )
{
int nextNode;                // Next node to visit
int i;

nextNode = s.pop();

if ( ! visited[nextNode] )
{
visited[nextNode] = true;    // Mark node as visited
System.out.println("nextNode = " + nextNode );

for ( i = NNodes-1; i >= 0; i-- )
if ( adjMatrix[nextNode][i] > 0 && ! visited[i] )
s.push(i);
}
}
}```

This code shows the implementation of a Breadth first search using a stack

This code is showing the set up of a graph and insertion methods. It is named wrongly

This code is for a Depth first search, not a Breadth first search

This code shows the implementation of a Breadth first search but instead of 'stack' it should be using a 'queue'