(using book: data structures and algorithms 2nd edition)

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

Modify the dfs.java program (Listing 13.1) to use adjacency lists rather than an

adjacency matrix. You can obtain a list by adapting the Link and LinkList

classes from the linkList2.java program (Listing 5.2) in Chapter 5. Modify the

find() routine from LinkList to search for an unvisited vertex rather than for a

key value.

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

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

LISTING 5.2 The linkList2.java Program

// linkList2.java

// demonstrates linked list

// to run this program: C>java LinkList2App

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

class Link

{

public int iData; // data item (key)

public double dData; // data item

public Link next; // next link in list

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

public Link(int id, double dd) // constructor

{

iData = id;

dData = dd;

}

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

public void displayLink() // display ourself

{

System.out.print({ + iData + , + dData + } );

}

} // end class Link

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

class LinkList

{

private Link first; // ref to first link on list

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

public LinkList() // constructor

{

first = null; // no links on list yet

}

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

public void insertFirst(int id, double dd)

{ // make new link

Link newLink = new Link(id, dd);

newLink.next = first; // it points to old first link

first = newLink; // now first points to this

}

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

public Link find(int key) // find link with given key

{ // (assumes non-empty list)

Link current = first; // start at first

while(current.iData != key) // while no match,

{

if(current.next == null) // if end of list,

return null; // didnt find it

else // not end of list,

current = current.next; // go to next link

}

return current; // found it

}

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

public Link delete(int key) // delete link with given key

{ // (assumes non-empty list)

Link current = first; // search for link

Link previous = first;

while(current.iData != key)

{

if(current.next == null)

return null; // didnt find it

else

{

previous = current; // go to next link

current = current.next;

}

} // found it

if(current == first) // if first link,

first = first.next; // change first

else // otherwise,

previous.next = current.next; // bypass it

return current;

}

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

public void displayList() // display the list

{

System.out.print(List (first-->last): );

Link current = first; // start at beginning of list

while(current != null) // until end of list,

{

current.displayLink(); // print data

current = current.next; // move to next link

}

System.out.println();

}

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

} // end class LinkList

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

class LinkList2App

{

public static void main(String[] args)

{

LinkList theList = new LinkList(); // make list

theList.insertFirst(22, 2.99); // insert 4 items

theList.insertFirst(44, 4.99);

theList.insertFirst(66, 6.99);

theList.insertFirst(88, 8.99);

theList.displayList(); // display list

Link f = theList.find(44); // find item

if( f != null)

System.out.println(Found link with key + f.iData);

else

System.out.println(Cant find link);

Link d = theList.delete(66); // delete item

if( d != null )

System.out.println(Deleted link with key + d.iData);

else

System.out.println(Cant delete link);

theList.displayList(); // display list

} // end main()

} // end class LinkList2App

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

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.addVertex('F'); // 5

theGraph.addVertex('G'); // 6

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

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

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

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

theGraph.addEdge(2, 3); // CD

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

theGraph.addEdge(2, 5); // CF

theGraph.addEdge(3, 6); // DG

theGraph.displayAdjLists(); // display adjacency lists

System.out.print("Visits: ");

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

System.out.println();

} // end main()

You MUST get this output in form and content:

Result:

A list: D C B

B list: E A

C list: F E D A

D list: G C A

E list: C B

F list: C

G list: D

Visits: A D G C F E B