graph.java package dsf_matrix_forStudents; /* * class: Graph * csc 2720, Spring

ID: 3817594 • Letter: G

Question

graph.java

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

/*
* 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

Explanation / Answer

Hi,

Below is the completed code :

package practice;

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()

}

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<MAX_VERTS; y++) // set adjacency
for(int x=0; x<MAX_VERTS; x++) // matrix to 0
adjMatrix[x][y] = 0;
theStack = new Stack();
} // end constructor
//add vertex
public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
//add edge
public void addEdge(int start, int end)
{
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
//display vertax
public void displayVertex(int v)
{
System.out.print(vertexList[v].data+" ");
}
/*
* depth-first search: Stack_based
*
*/
public void dfs()
{
   boolean[] visited= new boolean[nVerts];

   theStack.push(0);

   int v;
while (!theStack.isEmpty())
{
v = theStack.peek();
theStack.pop();

if (!visited[v])
{
   displayVertex(v);
visited[v] = true;
}
for(int i=0;i<nVerts;i++)
{
   int j=adjMatrix[v][i];
   if(j==1)
   {
   if (!visited[i])
theStack.push(i);

   }
}

}
}
/*
* depth-first search: Recursive
*/
public void recusive_dfs(int start)
{
boolean[] visited= new boolean[nVerts];
DFSUtil(start, visited);
}

public void DFSUtil(int v, boolean visited[])
{
visited[v] = true;
displayVertex(v); // OR System.out.print(v+" "); to get the vertex number

for(int i=0;i<nVerts;i++)
{
   int j=adjMatrix[v][i];
   if(j==1)
   {
   if (!visited[i])
DFSUtil(i, visited);
   }
}

}
} // end class Graph

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

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); }
}

NOTE : there can be multiple DFS traversals of the same tree.

feel free to ask if you have any doubt :)

Navigate

graph.c #include <stdio.h> #include <stdlib.h> typedef enum {FALSE, TRUE} bool;

graph1.txt: 6 8 Write a program to compute the Jaccard similarity between two ve

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

graph.java package dsf_matrix_forStudents; /* * class: Graph * csc 2720, Spring

Question

Explanation / Answer

Related Questions

Navigate