Modify this program to display the needed output as it is posted. The program di
ID: 3718458 • Letter: M
Question
Modify this program to display the needed output as it is posted. The program displays the first part of the desired output but doesnt display the second part please modify the program so it can display the output posted. Please solve it without modifying the main() method. (using book: data structures and algorithms 2nd edition)
Modify the dfs.java program to display a connectivity table for a
directed graph, as described in the section “Connectivity in Directed Graphs.”
desired output (in form and content ) :
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
Program to modify:
//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()
{
st = new int[SIZE];
top = -1;
}
////////////////////////////////////////////////////////////////
public void push(int j)
{
st[++top] = j;
}
//////////////////////////////////////////////////////////////
public int pop()
{
return st[top--];
}
/////////////////////////////////////////////////////////////
public int peek() {
return st[top];
}
/////////////////////////////////////////////////////////////
public boolean isEmpty() {
return top == -1;
}
////////////////////////////////////////////////////////////////
} ////END 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
// //////////////////////////////////////////////////////////////
// uses Vertex class from ch13ex1BreadthFirstMinSpanTree.java
class DFSLink
{
public int vertex;
public DFSLink next;
}
class DFSList {
public DFSLink head;
public DFSList() {
head = new DFSLink();
// head is given a dummy value so searches
// don't necessarily include vertex A (0)
head.vertex = -1;
}
public void insert(int v) {
DFSLink cur = head;
while (cur.next != null)
cur = cur.next;
cur.next = new DFSLink();
cur.next.vertex = v;
}
public DFSLink deleteFromEnd() {
if (head == null)
return null;
DFSLink cur = head;
while (cur.next.next != null)
cur = cur.next;
DFSLink temp = cur.next;
cur.next = null;
return temp;
}
public boolean contains(int j) {
DFSLink cur = head;
while (cur != null) {
if (cur.vertex == j)
return true;
cur = cur.next;
}
return false;
}
}
////////end Added or Modified
class DFSGraph {
private final int MAX_VERTS = 20;
private Vertex[] vertexList;
private DFSList[] adjMat;
private int nVerts;
private StackX theStack;
/////////////////////////////////////////////////////////////////
public DFSGraph()
{
vertexList = new Vertex[MAX_VERTS];
adjMat = new DFSList[MAX_VERTS];
nVerts = 0;
for (int j = 0; j < MAX_VERTS; j++)
adjMat[j] = new DFSList();
theStack = new StackX();
}
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);
}
// creates an edge from one vertex to another.
// DIRECTED GRAPH, not undirected
public void addEdge(int start, int end)
{
adjMat[start].insert(end);
}
public void displayVertex(int j) {
System.out.print(vertexList[j].label);
}
// modified to allow specification of a starting vertex
public void dfs(int start)
{
vertexList[start].wasVisited = true;
displayVertex(start);
theStack.push(start);
while (!theStack.isEmpty())
{
int v = getAdjUnvisitedVertex(theStack.peek());
if (v == -1)
theStack.pop();
else {
vertexList[v].wasVisited = true;
displayVertex(v);
theStack.push(v);
}
}
System.out.println();
for (int j = 0; j < nVerts; j++)
vertexList[j].wasVisited = false;
}
public int getAdjUnvisitedVertex(int v)
{
for (int j = 0; j < nVerts; j++)
if (adjMat[v].contains(j) && vertexList[j].wasVisited == false)
return j;
return -1;
}
public void displayConnectivityTable()
{
for (int j = 0; j < nVerts; j++)
dfs(j);
}
} // end class DFSGraph
//DFSApp.java:
class Main
{
public static void main(String[] args)
{
DFSGraph theGraph = new DFSGraph();
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 of the Directed Graph:");
theGraph.displayConnectivityTable();
System.out.println();
} // end main()
}
Modify this program to display the needed output as it is posted. The program displays the first part of the desired output but doesnt display the second part. Please solve it without modifying the main() method.
Modify the dfs.java program to display a connectivity table for a
directed graph, as described in the section “Connectivity in Directed Graphs.”
desired output (in form and content ) :
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
Program to modify:
//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()
{
st = new int[SIZE];
top = -1;
}
////////////////////////////////////////////////////////////////
public void push(int j)
{
st[++top] = j;
}
//////////////////////////////////////////////////////////////
public int pop()
{
return st[top--];
}
/////////////////////////////////////////////////////////////
public int peek() {
return st[top];
}
/////////////////////////////////////////////////////////////
public boolean isEmpty() {
return top == -1;
}
////////////////////////////////////////////////////////////////
} ////END 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
// //////////////////////////////////////////////////////////////
// uses Vertex class from ch13ex1BreadthFirstMinSpanTree.java
class DFSLink
{
public int vertex;
public DFSLink next;
}
class DFSList {
public DFSLink head;
public DFSList() {
head = new DFSLink();
// head is given a dummy value so searches
// don't necessarily include vertex A (0)
head.vertex = -1;
}
public void insert(int v) {
DFSLink cur = head;
while (cur.next != null)
cur = cur.next;
cur.next = new DFSLink();
cur.next.vertex = v;
}
public DFSLink deleteFromEnd() {
if (head == null)
return null;
DFSLink cur = head;
while (cur.next.next != null)
cur = cur.next;
DFSLink temp = cur.next;
cur.next = null;
return temp;
}
public boolean contains(int j) {
DFSLink cur = head;
while (cur != null) {
if (cur.vertex == j)
return true;
cur = cur.next;
}
return false;
}
}
////////end Added or Modified
class DFSGraph {
private final int MAX_VERTS = 20;
private Vertex[] vertexList;
private DFSList[] adjMat;
private int nVerts;
private StackX theStack;
/////////////////////////////////////////////////////////////////
public DFSGraph()
{
vertexList = new Vertex[MAX_VERTS];
adjMat = new DFSList[MAX_VERTS];
nVerts = 0;
for (int j = 0; j < MAX_VERTS; j++)
adjMat[j] = new DFSList();
theStack = new StackX();
}
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);
}
// creates an edge from one vertex to another.
// DIRECTED GRAPH, not undirected
public void addEdge(int start, int end)
{
adjMat[start].insert(end);
}
public void displayVertex(int j) {
System.out.print(vertexList[j].label);
}
// modified to allow specification of a starting vertex
public void dfs(int start)
{
vertexList[start].wasVisited = true;
displayVertex(start);
theStack.push(start);
while (!theStack.isEmpty())
{
int v = getAdjUnvisitedVertex(theStack.peek());
if (v == -1)
theStack.pop();
else {
vertexList[v].wasVisited = true;
displayVertex(v);
theStack.push(v);
}
}
System.out.println();
for (int j = 0; j < nVerts; j++)
vertexList[j].wasVisited = false;
}
public int getAdjUnvisitedVertex(int v)
{
for (int j = 0; j < nVerts; j++)
if (adjMat[v].contains(j) && vertexList[j].wasVisited == false)
return j;
return -1;
}
public void displayConnectivityTable()
{
for (int j = 0; j < nVerts; j++)
dfs(j);
}
} // end class DFSGraph
//DFSApp.java:
class Main
{
public static void main(String[] args)
{
DFSGraph theGraph = new DFSGraph();
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 of the Directed Graph:");
theGraph.displayConnectivityTable();
System.out.println();
} // end main()
}
Explanation / Answer
Code:
//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()
{
st = new int[SIZE];
top = -1;
}
////////////////////////////////////////////////////////////////
public void push(int j)
{
st[++top] = j;
}
//////////////////////////////////////////////////////////////
public int pop()
{
return st[top--];
}
/////////////////////////////////////////////////////////////
public int peek() {
return st[top];
}
/////////////////////////////////////////////////////////////
public boolean isEmpty() {
return top == -1;
}
////////////////////////////////////////////////////////////////
} ////END 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
// //////////////////////////////////////////////////////////////
// uses Vertex class from ch13ex1BreadthFirstMinSpanTree.java
class DFSLink
{
public int vertex;
public DFSLink next;
}
class DFSList {
public DFSLink head;
public DFSList() {
head = new DFSLink();
// head is given a dummy value so searches
// don't necessarily include vertex A (0)
head.vertex = -1;
}
public void insert(int v) {
DFSLink cur = head;
while (cur.next != null)
cur = cur.next;
cur.next = new DFSLink();
cur.next.vertex = v;
}
public DFSLink deleteFromEnd() {
if (head == null)
return null;
DFSLink cur = head;
while (cur.next.next != null)
cur = cur.next;
DFSLink temp = cur.next;
cur.next = null;
return temp;
}
public boolean contains(int j) {
DFSLink cur = head;
while (cur != null) {
if (cur.vertex == j)
return true;
cur = cur.next;
}
return false;
}
}
////////end Added or Modified
class DFSGraph {
private final int MAX_VERTS = 20;
private Vertex[] vertexList;
private DFSList[] adjMat;
private int nVerts;
private StackX theStack;
/////////////////////////////////////////////////////////////////
public DFSGraph()
{
vertexList = new Vertex[MAX_VERTS];
adjMat = new DFSList[MAX_VERTS];
nVerts = 0;
for (int j = 0; j < MAX_VERTS; j++)
adjMat[j] = new DFSList();
theStack = new StackX();
}
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);
}
// creates an edge from one vertex to another.
// DIRECTED GRAPH, not undirected
public void addEdge(int start, int end)
{
adjMat[start].insert(end);
}
public void displayVertex(int j) {
System.out.print(vertexList[j].label);
}
// modified to allow specification of a starting vertex
public void dfs(int start)
{
vertexList[start].wasVisited = true;
displayVertex(start);
theStack.push(start);
while (!theStack.isEmpty())
{
int v = getAdjUnvisitedVertex(theStack.peek());
if (v == -1)
theStack.pop();
else {
vertexList[v].wasVisited = true;
displayVertex(v);
theStack.push(v);
}
}
System.out.println();
for (int j = 0; j < nVerts; j++)
vertexList[j].wasVisited = false;
}
public int getAdjUnvisitedVertex(int v)
{
for (int j = 0; j < nVerts; j++)
if (adjMat[v].contains(j) && vertexList[j].wasVisited == false)
return j;
return -1;
}
public void displayConnectivityTable()
{
for (int j = 0; j < nVerts; j++)
dfs(j);
displayTable(); //to display the table
}
public void displayTable(){
char nodes[]={'A','B','C','D','E'};
System.out.println(" A B C D E");
System.out.println("====================================================");
for(int i=0;i<nVerts;i++){
System.out.print(" "+nodes[i]+" ");
for(int j=0;j<nVerts;j++){
if(adjMat[i].contains(j))
System.out.print("1 ");
else
System.out.print("0 ");
}
}
}
} // end class DFSGraph
//DFSApp.java:
class Main
{
public static void main(String[] args)
{
DFSGraph theGraph = new DFSGraph();
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 of the Directed Graph:");
theGraph.displayConnectivityTable();
System.out.println();
} // end main()
}
Sample output:
radas-macOS:Desktop radas$ java Main
Connectivity Table of the Directed Graph:
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.