1. Do a depth-first search of this graph starting with node S. When you have the choice of two or more edges to unexplored nodes to traverse, take the shortest edge first. List the discovery and finishing times of each node in the table below. If your depth first search from S ends without exploring all nodes of the graph (it will), continue the search from the unexplored node with the earliest letter of the alphabet.

Vertex

A

D

E

F

I

K

L

N

O

P

Q

S

Discovery Time

1

Finishing Time

2. List the type of each edge in the above graph using the table below.

Edge

AE

DK

DQ

EQ

FA

FL

FO

IP

KD

KE

LO

NI

NL

ON

PN

QA

SK

Type (BCFT)

3. Create the stack of nodes in reverse order of finishing time, with the latest finish time at the top. List that in the table below.

Top of Stack