Write an Algorithm for Graph Traversal ? The Graph has a loop.
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

   



Interview Questions and Answers

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


Related Questions

  Can you provide some implementation of a Dictionary having large number of words ?
 In a Linked list with sorted numbers, insert a new numbers while maintaining the sort order.
 What is the difference between Graph's Breadth first and Depth First algorithm ?
  What are the pre-requisite for the collection to perform Binary Search ?
 Explain various Searching and Sorting Algorithms ?
 Write a program for LinkedList, with method to append node and traversing the list ?
  Which sorting algorithm is used by Collections.sort() in Java ?
  How to determine if the linked list has a cycle in it ?
 Write an algorithm / java program for Heap Sort ?



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: