Algorithmic:

$1.$ Given the following directed graph:

A$.$ Find the shortest path length from vertex A to any other vertex in the graph by running the BFS algorithm.

B$.$ Extend the BFS algorithm so that for each vertex it prints the shortest path from S to it$.$

$2.$ Let $=(,)$ be an undirected graph and let $$ in $$ be a vertex in the graph. Find the length of the track

$($number of sides$)$ the shortest odd from $$ for every $$ in $.$

Instruction: use reduction to BFS$.$

$3.$ Let G be an undirected graph that is not bipartite. In the lecture it was proved that such a graph necessarily contains an odd circle. Extend the BFS algorithm and the algorithm that prints the trajectories to print this circuit.

$4.$ We will define a weighted graph to be a graph in which each arc has a numerical value. In such a graph the weight of a track will be the sum of the weights of the arcs on the track.

Let $=(,)$ be a graph where the weights on the arcs are $1,2$ or $3.$

Build an algorithm that finds the minimum path weight from a vertex S to all other vertices.

Tutorial: A reduction that will build a graph where the weights are $1$ and run BFS on it$.$

$5.$ Given the following directed graph:

V$=\{1,2,3,4,5,6,7,8,9\}$

E$=\{(1,2),(2,1),(2,5),(3,2),(4,5),(5,6),(6,3),(7,4),(7,8),(8,5),(8,9),(9,6)\}$

A$.$ Run DFS on the vertices. Select the vertices in the order in which they appear in V

$($from left to right$).$ Infer from the run whether there is a circle.

B$.$ Find the well$-$connected components of the graph

third. Add lines of code to the algorithm so that at the end the memory array is returned for each vertex

Which component does it belong to$?$

$6.$ In a directed graph, a vertex u will be called a leaf if every vertex of the graph has a route to u$.$ registered

An efficient algorithm that finds all the leaves of the graph. Analyze its effectiveness.