Algorithm - Interview Questions and Answers for 'Graph traversal' | Search Interview Question

Algorithm - Interview Questions and Answers for 'Graph traversal' - 7 question(s) found - Order By Newest

Q1. What is the difference between Graph's Breadth first and Depth First algorithm ?

Ans. In Breadth first algorithm, all the adjacent nodes of the starting node is visited first and then the same rule is followed while moving inwards whereas

In Depth first algorithm, all the nodes of a single traversal path are visited first till a cycle or an end is found.

For example , given the following entries of adjacent nodes

1,2
1,3
1,6
2,4
2,5
3,6

The Breadth first path would be

1,2,3,6,4,5

and Depth first path would be

1,2,4,5,3,6

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve graph traversal breadth first vs depth first frequent}

Q2. Write a Program for Graph Depth First Traversal using Apache Commons MultiMap

Algorithm

Ans. import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Multimap;

public class Graph {
   private static Multimap<Integer,Integer> adjacentDirectedNodesMap = ArrayListMultimap.create();
   private static Set<Integer> alreadyVisited = new HashSet();

   static{
      adjacentDirectedNodesMap.put(1, 2);
      adjacentDirectedNodesMap.put(1, 3);
      adjacentDirectedNodesMap.put(1, 5);
      adjacentDirectedNodesMap.put(2, 4);
      adjacentDirectedNodesMap.put(4, 5);
   }

   public static void main(String[] args){
      ArrayList visited = new ArrayList();

      Integer startNode = 1;

      displayAdjacentNodes(startNode);

   }

   private static void displayAdjacentNodes(Integer integer){
      if(alreadyVisited.contains(integer)){
         return;
      }
      alreadyVisited.add(integer);
      System.out.println(integer);
      for(Integer adjacentNodes: adjacentDirectedNodesMap.get(integer)){
         displayAdjacentNodes(adjacentNodes);
      }
   }

}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve graph traversal depth first algorithm}

Q3. Write a Program for Graph Breadth First Traversal using Apache Commons MultiMap

Ans. import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Multimap;

public class Graph {
   private static Multimap<Integer,Integer> adjacentDirectedNodesMap = ArrayListMultimap.create();
   private static Set<Integer> alreadyVisited = new HashSet();

   static{
      adjacentDirectedNodesMap.put(1, 2);
      adjacentDirectedNodesMap.put(1, 3);
      adjacentDirectedNodesMap.put(1, 5);
      adjacentDirectedNodesMap.put(2, 4);
      adjacentDirectedNodesMap.put(4, 5);
   }

   public static void main(String[] args){
      ArrayList visited = new ArrayList();

      Integer startNode = 1;

      displayAdjacentNodes(startNode);

   }

   private static void displayAdjacentNodes(Integer integer){
      System.out.println(integer);
      for(Map.Entry<Integer, Collection<Integer>> adjacentNodes: adjacentDirectedNodesMap.asMap().entrySet()){
         for(Integer integer1:adjacentNodes.getValue()){
            if(alreadyVisited.contains(integer1)){
               continue;
            }
            alreadyVisited.add(integer1);
            System.out.println(integer1);
         }
      }
   }

}

Sample Code for import java.util.ArrayList; import java.util.Collection; import java.util.HashSet; import java.util.Map; import java.util.Set; import com.google.common.collect.ArrayListMultimap; import com.google.common.collect.Multimap;

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve graph traversal breadth first traversal}

Q4. Write an Algorithm for Graph Traversal ? The Graph has a loop.

Algorithm

Ans. Please not that all such questions can be easily answered through recursion.

Simple recursive implementation could be

traverse(root);

void traverse(Element element){
if(element.hasNext()){
traverse(element.next());
} else {
System.out.println(element);
}
}

but this algo / code lead to endless loop if there is a loop in graph traversal.

So you can keep a collection to keep track of which elements have laready been traversed

static List<Elements> listOfAlreadyTraversedElements = new ArrayList<Elements>();

main(){
traverse(root);
}

void traverse(Element element){
if(element.hasNext()){
traverse(element.next());
} else {
listOfAlreadyTraversedElements.add(element);
System.out.println(element);
}
}

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve graph traversal algorithm graph traversal algorithm using recursion Asked in 1 Companies intermediate}

Q5. Given the list of adjacent nodes, What will be the Breadth First path

1 -> 2
1 -> 3
1 -> 6
2 -> 4
3 -> 5

Algorithm

Ans. 1 -> 2 -> 3 -> 6 -> 4 - > 5

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve breadth first traversal graph traversal}

Q6. Given the list of adjacent nodes, What will be the Depth First path

1 -> 2
1 -> 3
1 -> 6
2 -> 4
3 -> 5

Algorithm

Ans. 1 -> 2 -> 4 -> 3 -> 5 -> 6

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve depth first traversal graph traversal}

Q7. What will happen in a graph traversal if we don't have a check for cycle

Algorithm

Ans. It will result in never ending loop

Help us improve. Please let us know the company, where you were asked this question :

_{Like Discuss Correct / Improve graph traversal}

Search Interview Questions

Help us and Others Improve. Please let us know the questions asked in any of your previous interview.