Question

1. Explain the significance of Breadth-First Search in graphs and its time complexity. List down any 4 (four) applications of Breadth-First Search in details. (6 marks) 2. Do you agree to use Stack data structure in backtracking technique for game development? Justify your answer with an example. (6 marks)

Answer 1

1)BFS is Breadth first search.This algorithm selects a single node in a graph and then visits all the nodes adjacent to the selected node.Once BFS visits and marks the starting node, then it moves towards the nearest unvisited nodes and analyses them. all nodes are marked when once visited. until all the nodes of the graph have been visited and marked these iterations continue.

->It helps find shortest path while traversing in smallest number of iterations.

->It is more accurate when compared to other algorithms.

time complexity:

O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.

V * (O(1) + O(Eaj) + O(1))
V + V * Eaj + V
2V + E(total number of edges in graph)
V + E

applications:

Network broadcasting,web crawlers,P2P networks,unweighted graph,navigation systems.

2)stack follows LIFO procedure.backtracking considers searching every possible way for solving a computational problem.

So if you consider looking for a path in a game to complete in shortest moves.It visits the first choice and moves to the next one if it cant find the best possible choice, it backtracks the previous choice and takes the other path checking for in depth and all possible opportunities.