Implement a method to traverse the nodes in a graph using Breadth First Search Algorithm. Your method should return an ArrayList of strings in expected order.
Example: apple / \ banana mango / \ / peach strawberry \ / cherry Output : apple mango banana strawberry peach cherry
adjacent nodes
before searcing its grandchildren nodes
. The best iterative approach would be to use queue
to keep track of the visited nodes
.While traversing through the nodes, print the data of the nodes with a single space
Using queue
to traverse through the nodes to search for the data, the step by step approach would be as below.
1. If the root node
is not null
, return proceed to next step.
2. Declare and initialize a queue
object, to deal with the Node
objects.
3. Add the root node
to the queue
and mark it's visited
property to true.
4. Start a loop
to run till the queue
becomes empty
.
5. Poll
an object from the queue
. Print its data with a single space.
6. Traverse through all its adjacent nodes
through the use of a loop
and mark its visited
property to true
and add them to the queue
.
7. End of the loop will make sure that the traversal is complete.
public ArrayList<String> breadthFirstTraversal(Node rootNode){ }
C
Java
Python