Please solve the problem and post the entire program and the whole output:

Modify the dfs.java program (Listing 13.1) to display a connectivity table for a

directed graph, as described in the section Connectivity in Directed Graphs.

LISTING 13.1 The dfs.java Program

// dfs.java

// demonstrates depth-first search

// to run this program: C>java DFSApp

////////////////////////////////////////////////////////////////

class StackX

{

private final int SIZE = 20;

private int[] st;

private int top;

// -----------------------------------------------------------

public StackX() // constructor

{

st = new int[SIZE]; // make array

top = -1;

}

// -----------------------------------------------------------

public void push(int j) // put item on stack

{ st[++top] = j; }

// -----------------------------------------------------------

public int pop() // take item off stack

{ return st[top--]; }

// ------------------------------------------------------------

public int peek() // peek at top of stack

{ return st[top]; }

// ------------------------------------------------------------

public boolean isEmpty() // true if nothing on stack-

{ return (top == -1); }

// ------------------------------------------------------------

} // end class StackX

////////////////////////////////////////////////////////////////

class Vertex

{

public char label; // label (e.g. A)

public boolean wasVisited;

// ------------------------------------------------------------

public Vertex(char lab) // constructor

{

label = lab;

wasVisited = false;

}

// ------------------------------------------------------------

} // end class Vertex

////////////////////////////////////////////////////////////////

class Graph

{

private final int MAX_VERTS = 20;

private Vertex vertexList[]; // list of vertices

private int adjMat[][]; // adjacency matrix

private int nVerts; // current number of vertices

private StackX theStack;

// -----------------------------------------------------------

public Graph() // constructor

{

vertexList = new Vertex[MAX_VERTS];

// adjacency matrix

adjMat = new int[MAX_VERTS][MAX_VERTS];

nVerts = 0;

for(int j=0; j

for(int k=0; k

adjMat[j][k] = 0;

theStack = new StackX();

} // end constructor

// -----------------------------------------------------------

public void addVertex(char lab)

{

vertexList[nVerts++] = new Vertex(lab);

}

// -----------------------------------------------------------

public void addEdge(int start, int end)

{

adjMat[start][end] = 1;

adjMat[end][start] = 1;

}

// ------------------------------------------------------------

public void displayVertex(int v)

{

System.out.print(vertexList[v].label);

}

// ------------------------------------------------------------

public void dfs() // depth-first search

{ // begin at vertex 0

vertexList[0].wasVisited = true; // mark it

displayVertex(0); // display it

theStack.push(0); // push it

while( !theStack.isEmpty() ) // until stack empty,

{

// get an unvisited vertex adjacent to stack top

int v = getAdjUnvisitedVertex( theStack.peek() );

if(v == -1) // if no such vertex,

theStack.pop();

else // if it exists,

{

vertexList[v].wasVisited = true; // mark it

displayVertex(v); // display it

theStack.push(v); // push it

}

} // end while

// stack is empty, so were done

for(int j=0; j

vertexList[j].wasVisited = false;

} // end dfs

// ------------------------------------------------------------

// returns an unvisited vertex adj to v

public int getAdjUnvisitedVertex(int v)

{

for(int j=0; j

if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)

return j;

return -1;

} // end getAdjUnvisitedVertex()

// ------------------------------------------------------------

} // end class Graph

////////////////////////////////////////////////////////////////

class DFSApp

{

public static void main(String[] args)

{

Graph theGraph = new Graph();

theGraph.addVertex(A); // 0 (start for dfs)

theGraph.addVertex(B); // 1

theGraph.addVertex(C); // 2

theGraph.addVertex(D); // 3

theGraph.addVertex(E); // 4

theGraph.addEdge(0, 1); // AB

theGraph.addEdge(1, 2); // BC

theGraph.addEdge(0, 3); // AD

theGraph.addEdge(3, 4); // DE

System.out.print(Visits: );

theGraph.dfs(); // depth-first search

System.out.println();

} // end main()

} // end class DFSApp

////////////////////////////////////////////////////////////////

Use this MAIN method below (Do NOT modify it) :

public static void main(String[] args)

{

Graph theGraph = new Graph();

theGraph.addVertex('A'); // 0 (start for dfs)

theGraph.addVertex('B'); // 1

theGraph.addVertex('C'); // 2

theGraph.addVertex('D'); // 3

theGraph.addVertex('E'); // 4

theGraph.addEdge(0, 2); // AC

theGraph.addEdge(1, 0); // BA

theGraph.addEdge(1, 4); // BE

theGraph.addEdge(3, 4); // DE

theGraph.addEdge(4, 2); // EC

System.out.println("Connectivity Table");

theGraph.makeTable();

System.out.println(" ");

theGraph.adjMatDisplay();

} // end main()

You MUST get this output in form and content:

Result:

Connectivity Table

AC

BACE

C

DEC

EC

A B C D E

==========

A 0 0 1 0 0

B 1 0 0 0 1

C 0 0 0 0 0

D 0 0 0 0 1

E 0 0 1 0 0