JAVA Question

Standard DFS $(V,E$;$s_0)$

Input: $,G=(V,E)$ a digraph and $s_0$inV

The vertices in $V$ are colored white, gray or black

so is uhite.

Output Application dependent

Color $s_0$ as gray, and VISIT$(s_0)$

for each $v$ adjacent to $s_0$ do

PREVISIT$(v,s_0)$

if $(v$ is white$)$ then

Standard DFS $((V,E$;$v))$ Recursive call

Color $s_0$ black, and POSTVISIT$(s_0).$

Standard DFS is a recursive program contain three "macros":

Think of macros as simple subroutines that executes a few basic instructions

$($so it has $O(1)$ complexity$).$ For instance, it might contain a single assignment

statement

$=1[u]larr$ clock $++$

to set the finish time of node $u.$ Thus, until we specify these macros, the

Standard DFS is not fully specified. The vertices of $G$ are initially all uhite,

but each time we call the Standard DFS$,$ some of their color changes. The

color transitions may be correlated with the macros:

white $$VISIT gray POSTVISIT black.

It is useful to view PREVISIT$(v,u)$ as "visiting the edge $u-v".$

How do we ensure that the precondition of Standard DFS that vertices of $G$

must be colored white$/$gray$/$black$?$ This precondition can be fulfilled if we

assume that the Standard DFS is called by another routine called the DFS

Driver:

Note that there are $4$ Driver macros:

To implement any of the DFS$-$based algorithms, it remains for us to specify

these $3+4=7$ macros. By default, a macro is assumed to be NO$-$OP $($i$.$e$.,$

empty$)$ unless we specify it$.$ In this exercise, we ask you to specify these

macros.

For example, if we want to assign discovery$-$time and finish$-$time to

nodes, the DRIVER$\_$INIT $(G)$ macro must to initialize two arrays

$d[1.n]$ and $f[1$dotsn$]($assuming $V=(1.n)).$ We also need a clock

variable to be initialized to $0($or $1).$ Notioe that all these are global

variables that recursive DFS can access.

Let DFS Pair refer to the pair of algorithms $($DFS Driver, Standard DFS$).$

In the following, we want you to specify the $7$ macros of the DFS Pair in in

order to solve various problems. You only have to explicitly program those

macros that are not NO$-$OPs. We call this macro programming of the DFS

pair.

$($a$)$ Please program the macros of the DFS Pair so that re$-$produce the be$-$

havior of the Full DFS in Slides $6.$

Specifically, the Full DFS outputs the array $[1.n]$ representing the DFS

forest, and also the two arrays $d[1..n]$ and $f[1.n]$ for the discovery time

and finish time.

$($b$)$ Please program the macros of the DFS Pair in order to implement Tarjan's

Topological Sort Algorithm.

Specifically: Tarjan's algorithm produces a sequence $(v_1,$dots,$v_n)$ repre$-$

senting the topological sort.