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

  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

  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

  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

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

  depth_first_search_recursive(graph, next, visited)

  depth_first_search_recursive(start, next)

  visited.add(start)

  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:
depth_first_traversal1.png

   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

  Breadth Last Search

  Depth Last Search

  Breadth First Search

  Depth First Search

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

  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
dfs_whathappensnext_2.png

  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?
bfs_whathappensnext_1.png

  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?
bfs_possible_order_of_traversal.png

  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

 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 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'