Problem $1$ Graph Algorithms

$2$

Clearly indicate the following spanning trees in the weighted graph pictured below, assuming that node$-1$ is the start vertex. Some of them have more than one correct answer.

Note: You do not have to demionstrate the algorithm. Just denict the final recult

$($a$)$ A breadth$-$first spanning tree, with start node as $1$

$($b$)$ A depth$-$first spanning tree rooted, with start node as $1$

$($c$)$ A shortest$-$path spanning tree, with start node as $1$

$($d$)$ A minimum spanning tree

$($e$)$ A maximum spanning tree

Solution $1$

$($a$)$ Breadth$-$first spanning tree, rooted in $1.$

$($a$)$ Lepun$-$mst spanning tree, rooted in $1.$

$($a$)$ A shortest$-$path spanning tree, rooted in $1.($a$)$ Minimum spanning tree

$($a$)$ Maximum spanning tree

Problem $2$ Topological Ordering and Cycles

$5$ pts$.$

Most software projects consists of multiple modules that are interdependent on each other. For example, Module A may depend on Module B$,$ Module B may depend on Module C$,$ and Module C may depend on Module A$.$ This forms a cycle in the dependency graph, which can cause issues during the build process. Given the dependency graph on the various software modules, develop a single algorithm called TopoSortCycles $(G)$ on a dependency $($directed$)$ graph $G$ that does both of the following:

$($a$)$ Return the topological ordering of modules using DFS$\_$Topo $(G,s)$ subroutine $($given below$)$ to build the software.

$(2$ pts$)$

DFS$\_$Topo$(G,s,$ CurrentLabel$)$

$,$for each vertex vinG.$V$

$,,v.$ explored $=0$

$,$s$.$ explored $=1$

$,$for each vertex vinG.$V$

$,,$if $v.$ explored $=1$

$,,,$DFS$\_$TOPO $(G,v)$

$,$s$.$order $=$ CurrentLabel $//$ Assign position of $s$ in the topological ordering

$,$CurrentLabel $=$ CurrentLabel $-1$

$,$return CurrentLabel

$($b$)$ Detect any cycle in the dependency graph, in which case, it should throw an error and print the cycle.

$(3$ pts$)$

Solution $2$