data structures using if the number of vertices and edges in the graph are known ahead of timethe space complexity can also be expressed as )where is the total number of edges in and is the number of nodes or vertices time complexity in the worst casebreadth-first search has to traverse through all paths to all possible nodesthus the time complexity of this algorithm asymptotically approaches (bdhoweverthe time complexity can also be expressed as oe )since every vertex and every edge will be explored in the worst case completeness breadth-first search is said to be complete algorithm because if there is solutionbreadth-first search will find it regardless of the kind of graph but in case of an infinite graph where there is no possible solutionit will diverge optimality breadth-first search is optimal for graph that has edges of equal lengthsince it always returns the result with the fewest edges between the start node and the goal node but generallyin real-world applicationswe have weighted graphs that have costs associated with each edgeso the goal next to the start does not have to be the cheapest goal available applications of breadth-first search algorithm breadth-first search can be used to solve many problems such asfinding all connected components in graph finding all nodes within an individual connected component finding the shortest path between two nodesu and vof an unweighted graph finding the shortest path between two nodesu and vof weighted graph programming example write program to implement the breadth-first search algorithm #include #define max void breadth_first_search(int adj[][max],int visited[],int startint queue[max],rear - ,front = iqueue[++rearstartvisited[start while(rear !frontstart queue[++front]if(start = printf(" \ ")else printf("% \ ",start )for( maxi++if(adj[start][ = &visited[ = queue[++rearivisited[ int main(