Depth$-$first search for finding Strongly Connected Components.$$ Consider the directed graph below.$$ DO a DFS of this graph, when you have a choice of multiple unvisited nodes to visit next, go to the nearest one.$$ If two nodes are equally distance, break ties alphabetically. $(0\mathrm{.}2$ points per box $[$minus the three that I$$ve already filled$])$

Part A: Find the discovery and finish times of the nodes.

Solution:

Node

A

B

C

D

E

F

G

Discovery Time

$$

$$

$$

$$

$$

$$

Finishing Time

$$

$$

$$

$$

$$

$$

Part B:$$ Classify the edges as T $($tree$),$ F $($forward$),$ B $($back$),$ or C $($cross$)$ edges

Solution:

Edge

AB

AC

AD

BD

BE

CA

CF

DB

DC

DE

DF

DG

EG

FD

GE

Type

$$

$$

$$

$$

$$

$$

$$

$$

$$

$$

$$

$$

$$

$$

$$

Part C:$$ In the table below, show the stack that you generate using Kosaraju$$s algorithm.$$ Note that the top of the stack is on the left.

Stack

Top

$$

$$

$$

$$

$$

Bottom

Node

$$

$$

$$

$$

$$

$$

$$

Part D: Here$$s the graph G$($G with the edge directions reversed$).$ Show the discovery times and finish times of the nodes when you do a heuristic DFS$.$

Solution:

Node

A

B

C

D

E

F

G

Discovery Time

$$

$$

$$

$$

$$

$$

Finishing Time

$$

$$

$$

$$

$$

$$

$$

$$

Part E: List the SCCs$.($You may not need all the lines.$)$

Solution:

SCCs:$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$