graph.java

package dsf_matrix_forStudents; /* * class: Graph * csc 2720, Spring 2017 */

class Graph { private final int MAX_VERTS = 20; private Vertex vertexList[]; // list of vertices private int adjMatrix[][]; // adjacency matrix private int nVerts; // current number of vertices private Stack theStack; //------------------------------------------------------------ public Graph() // constructor { vertexList = new Vertex[MAX_VERTS]; // adjacency matrix adjMatrix = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for(int y=0; y

/* * depth-first search: Recursive */ public void recusive_dfs(int start) { //TO-DO } // end depthFirstSearch

} // end class Graph ////////////////////////////////////////////////////////////////

class Vertex { public char data; // data public boolean isVisited;

public Vertex(char d) // constructor { data = d; isVisited = false; }

} // end class Vertex

stack.java

package dsf_matrix_forStudents; /* * class: Stack * csc 2720, Spring 2017 */

class Stack { private final int SIZE = 50; private int[] st; private int top; //constructor public Stack() { st = new int[SIZE]; // make array top = -1; } // put item on stack public void push(int j) { st[++top] = j; } //take item off stack public int pop() { return st[top--]; } //peek at top of stack public int peek() { return st[top]; } //true if nothing on stack public boolean isEmpty() { return (top == -1); }

} // end class Stack

test.java

package dsf_matrix_forStudents; /* * class: Test * csc 2720, Spring 2017 */

public class Test { 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'); // 4

theGraph.addEdge(0, 1); // AB theGraph.addEdge(0, 2); // AC theGraph.addEdge(1, 3); // BD theGraph.addEdge(2, 4); // CE theGraph.addEdge(2, 3); // CD theGraph.addEdge(0, 3); // AD theGraph.addEdge(3, 4); // DE theGraph.addEdge(3, 5); // DE

System.out.print("Stack based dfs visits:----------------------- "); theGraph.dfs(); System.out.println(); System.out.print("recursive dfs visits:----------------------- "); theGraph.recusive_dfs(0); } // end main() } // end class DFSApp ////////////////////////////////////////////////////////////////

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

Adjacency matrix for Graph (a) (b) 1 2 3 4 6 7 8 W X P 0 0 1 0 0 1 0 0 0 1 Q 0 0 0 0 1 0 0 2 R 0 0 0 0 0 0 1 0 0 3 0 0 0 0 1 0 0 0 0 4 T 0 0 0 0 0 1 0 0 0 5 W 0 0 0 1 0 0 0 1 01 0 0 0 0 0 0 0 0 0 7 Y 0 0 1 0 0 0 0 0 1 8 z 0 0 0 0 0 0 0 0 0 a) A directed graph and b) its adjacency matrix