In a breadth-first traversal, we visit a node, then all the nodes on the next le
ID: 3576638 • Letter: I
Question
In a breadth-first traversal, we visit a node, then all the nodes on the next level from left to right, then all nodes on the 3rd level (from left to right) etc. For example, in the tree below, a breadth-first traversal would visit the nodes in the following order: a, b, c, d, e, f, g, h, i, j, k, l Write (on paper) a method to perform a breadth-first search traversal. As you visit each node, just print out its item. You can assume that this method has access to the instance variable 'root'. Use a queue in your solution (the algorithm is non-recursive). What is the time complexity (in big-O notation) for this method? Explain how you determined this. Just giving me the correct O() answer will only be half credit.Explanation / Answer
method for bfs :
public void bfs(int aa[][],int first)
{
int nodes = aa[first].length-1;
int[] v = new int[nodes + 1];
int i,elem;
v[first]=1;
queue.add(first);
while(!queue.isEmpty())
{
elem = queue.remove();
i = elem;
System.out.println(i+" ");
while(i<= nodes)
{
if(aa[elem][i] == 1 && v[i] == 0)
{
queue.add[i];
v[i]=1;
}
i++;
}
}
}
The time complexity is O(V^2) because here use adjacency matrix.