# CMPS 101 Programming Assignment 5

\$30.00

## Description

In this assignment you will build a Graph module in C that implements Depth First Search (DFS). You
will use your Graph module to find the strongly connected components of a digraph. Begin by reviewing
sections 22.3-22.5 of the text (3rd ed.)
A digraph
G  (V,E)
is said to be strongly connected iff for every pair of vertices
u,vV , vertex u is
reachable from v, and vertex v is reachable from u. Most directed graphs are not strongly connected. In
general we say a subset
X V
is strongly connected iff every vertex in X is reachable from every other
vertex in X. A strongly connected subset that is maximal with respect to this property is called a strongly
connected component of G. In other words,
X V
is a strongly connected component of G if and only
if (i) X is strongly connected, and (ii) the addition of one more vertex to X would create a subset that is not
strongly connected.
Example
1 2 3 4
G:
5 6 7 8
We can see that this digraph contains 4 strongly connected components:
{1, 2, 5} C1  , {3, 4} C2  ,
{6, 7} C3 
, and
{8} C4  .
To find the strong components of a digraph G call
DFS(G)
. As vertices are finished, place them on a
stack. When DFS is complete the stack stores the vertices ordered by decreasing finish times. Next
compute the transpose
T G
of G. (The digraph
T G
is obtained by reversing the directions on all edges of
G.) Finally run
DFS( )
T G
, but in the main loop (lines 5-7) of DFS, process vertices in order of decreasing
finish times from the first call to DFS. This is accomplished by popping vertices off the stack. When the
whole process is complete, the trees in the resulting DFS forest span the strong components of G. Note
that the strong components of G are identical to the strong components of
T G . See the algorithm
Strongly-Connected-Components and proof of correctness in section 22.5 of the text (3
rd ed.)
In this project you will again create a graph module in C using the adjacency list representation. Your
graph module will, among other things, provide the capability of running DFS, and computing the
transpose of a directed graph. DFS requires that vertices possess attributes for color (white, black, grey),
discover time, finish time, and parent. Here is a catalog of required functions and their prototypes:
/* Constructors-Destructors */
Graph newGraph(int n);
void freeGraph(Graph* pG);
/* Access functions */
int getOrder(Graph G);
int getSize(Graph G);