Search Interview Questions | ![]() ![]() Click here and help us by providing the answer. ![]() Click Correct / Improve and please let us know. |
|
| ||||
Algorithm - Interview Questions and Answers for 'Graph traversal' - 7 question(s) found - Order By Newest | ||||
| ||||
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 | ||||
![]() | ||||
![]() ![]() ![]() ![]() | ||||
| ||||
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); } } } | ||||
![]() | ||||
![]() ![]() ![]() | ||||
| ||||
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); } } } } | ||||
![]() | ||||
![]() | ||||
![]() ![]() ![]() | ||||
| ||||
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); } } | ||||
![]() | ||||
![]() ![]() ![]() ![]() ![]() | ||||
| ||||
Ans. 1 -> 2 -> 3 -> 6 -> 4 - > 5 | ||||
![]() | ||||
![]() ![]() ![]() | ||||
| ||||
Ans. 1 -> 2 -> 4 -> 3 -> 5 -> 6 | ||||
![]() | ||||
![]() ![]() ![]() | ||||
| ||||
Ans. It will result in never ending loop | ||||
![]() | ||||
![]() ![]() ![]() | ||||