1. Use Kosarajus algorithm to find the strongly connected components of the graph below. Do it according to the following steps.

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

1. Here is the complement of the graph above the graph with all its edges reversed. Do DFS on this graph following Kosarajus algorithm as shown in the notes, the text, or geeksforgeeks.org (same result). Show the start and finish times in the table below.

Vertex

A

D

E

F

I

K

L

N

O

P

Q

S

Discovery Time

1

Finishing Time

2. Based on the results of the algorithm, list the SCCs of this graph, one per line below (you may not need all the lines)

_______________________

_______________________

_______________________

_______________________

_______________________

_______________________

Transcribed image text