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

Interview Questions and Answers

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

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}