Algorithm - Interview Questions and Answers for 'Graph traversal' | Search Interview Question - javasearch.buggybread.com
Javasearch.buggybread.com

Search Interview Questions


 More than 3000 questions in repository.
 There are more than 900 unanswered questions.
Click here and help us by providing the answer.
 Have a video suggestion.
Click Correct / Improve and please let us know.
Label / Company      Label / Company / Text

   



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

 Q1. What is the difference between Graph's Breadth first and Depth First algorithm ?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 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


 Q3. 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


 Q4. 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


 Q5. What will happen in a graph traversal if we don't have a check for cycleAlgorithm
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



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

Any input from you will be highly appreciated and It will unlock the application for 10 more requests.

Company Name:
Questions Asked: