Consider the following directed graph:

For parts $($a$)-($d$),$ ignore the direction of the edges and treat the graph as undirected.

For the rest of the parts, treat the graph as directed. Whenever you need to make a

choice in an algorithm $($which node to consider first$),$ always choose the node that's

alphabetically earlier.

$($a$)$ Compute a BFS tree with the source being node $A.$

$($b$)$ Provide a shortest path between nodes A and $H.$ What is its length?

$($c$)$ Is the graph bipartite? If yes, provide a coloring showing that it is bipartite. If no$,$

explain why.

$($d$)$ If we add the edge $(E,K),$ does your answer to part $($c$)$ change?

$($e$)$ Find a topological ordering for this graph, or show that none exist.

$($f$)$ If we add the directed edge $(E,K),$ does your answer to part $($e$)$ change?

$($g$)$ If instead we add the directed edge $(K,E),$ does your answer to part $($e$)$ change?

$($h$)$ What are the nodes in the strongly connected component containing node E$?$ Is

the entire graph strongly connected? $($Warning: trick question!$)$

$($i$)$ Suppose we add the directed edge $(K,E).$ Does your answer to part $($h$)$ change,

and if so$-$ how?