Preview

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

zero ways

infinite ways (meaning all graphs cannot be traversed successfully)

one best and singular way

multiple ways

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

stacks

queues

vertices or nodes,

lines

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

breadth first search (BFS).

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

boolean visited array

recursive search function

path that cannot be travsersed easily

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.

Breadth-first search

Node-first search

Depth-last search

Depth-first 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 Breadth first (variations)

Both definitions are for Depth First

Definition 1 = Breadth first; Definition 2 = Depth first

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()
    visited.add(start)
    for next in graph[start] - visited:
        ???????????????????????????????????
    return visited

depth_first_search_recursive(graph, next, visited)

visited.add(start)

depth_first_search_recursive(next, visited, 1,0)

depth_first_search_recursive(start, next)

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 is a leaf 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 and v must have the same parent 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:

1,2,0,3

2, 0, 1, 3.

2,1,3,0

0,1,2,3

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

Breadth First Search

Breadth Last Search

Depth Last Search

Depth First Search

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

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

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

F' is added to the top of the stack and also to the 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

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

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

G', 'E', 'B' and 'A' come off the stack and 'D' is added to the stack and 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

pointer

stack

queue

iterative function

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

queue

iterative function

stack

pointer

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

shorst path from the root to the left most child node

shortest path from one vertex to another.

longest path from one vertex to another

shortest path from the root to the right most child node

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

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

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

B' and 'F' are removed from the queue, and 'E' is added to the queue and to 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

QNPMOR

QMNPRO

NQMPOR

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?

Only DFS

Neither BFS or DFS

Both BFS and DFS

Only BFS

20. Which of the following statements is most true about this Java code snippet.

   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 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 using a stack

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

Report an error