Answered step by step
Verified Expert Solution
Question
1 Approved Answer
so far this is what i have. the code works but graph 2 is a cyclic graph and j just want an if statement that
so far this is what i have. the code works but graph 2 is a cyclic graph and j just want an if statement that checks if it is a cycle. i dont want another code, i just want someone to update mine. thanks ! public class Vertex { private String name; private boolean visited; private List adjencyList; public Vertex(String name){ this.name = name; this.adjencyList = new ArrayList(); } public void addVerticesNeighbors(Vertex vertex){ this.adjencyList.add(vertex); } public String getName(){ return name; } public void setName(String name){ this.name = name; } public boolean isVisited(){ return visited; } public void setVisited(boolean visited){ this.visited = visited; } public List getAdjencyList(){ return adjencyList; } public void setAdjencyList(List adjencyList){ this.adjencyList = adjencyList; } @Override public String toString(){ return this.name; } } public class DFS { private Stack stack; public DFS(){ this.stack = new Stack(); } public void dfs(List vertexList){ for(Vertex v : vertexList){ if(!v.isVisited()){ v.setVisited(true); dfsWithStack(v); } } } private void dfsWithStack(Vertex rootVertex) { this.stack.add(rootVertex); rootVertex.setVisited(true); while (!stack.isEmpty()) { Vertex actualVertex = this.stack.pop(); System.out.print(actualVertex + " "); for (Vertex v : actualVertex.getAdjencyList()) { if (!v.isVisited()) { v.setVisited(true); this.stack.push(v); } } } } public class Data { /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here Vertex v1 = new Vertex("a"); Vertex v2 = new Vertex("b"); Vertex v3 = new Vertex("c"); Vertex v4 = new Vertex("d"); Vertex v5 = new Vertex("e"); Vertex v6 = new Vertex("f"); Vertex v7 = new Vertex("g"); List list = new ArrayList(); v1.addVerticesNeighbors(v2); v1.addVerticesNeighbors(v3); v2.addVerticesNeighbors(v7); v2.addVerticesNeighbors(v5); v3.addVerticesNeighbors(v6); v4.addVerticesNeighbors(v1); v4.addVerticesNeighbors(v2); v4.addVerticesNeighbors(v3); v4.addVerticesNeighbors(v6); v4.addVerticesNeighbors(v7); v7.addVerticesNeighbors(v6); v7.addVerticesNeighbors(v5); list.add(v1); list.add(v2); list.add(v3); list.add(v4); list.add(v5); list.add(v6); list.add(v7); System.out.println("Graph 1"); DFS dfs = new DFS(); dfs.dfs(list); System.out.println(); System.out.println("Graph 2"); Vertex v8 = new Vertex("a"); Vertex v9 = new Vertex("b"); Vertex v10 = new Vertex("c"); Vertex v11 = new Vertex("d"); Vertex v12 = new Vertex("e"); Vertex v13 = new Vertex("f"); Vertex v14 = new Vertex("g"); List list2 = new ArrayList(); v8.addVerticesNeighbors(v9); v9.addVerticesNeighbors(v10); v10.addVerticesNeighbors(v11); v11.addVerticesNeighbors(v14); v14.addVerticesNeighbors(v12); v12.addVerticesNeighbors(v8); v13.addVerticesNeighbors(v12); v13.addVerticesNeighbors(v9); v13.addVerticesNeighbors(v10); v13.addVerticesNeighbors(v14); list2.add(v8); list2.add(v9); list2.add(v10); list2.add(v11); list2.add(v12); list2.add(v13); list2.add(v14); DFS dfs2 = new DFS(); dfs2.dfs(list2); } } Data - NetBeans IDE 12 File Edit View Navigate Source Refector Run Debug Profile Team Tools Window Help T Q. Search Carlto . Graha xDrivendega x x Date Wertex Sex ...ave DataStructures. ava Source History Projects x Services Files Cws Data Source Pages data v12.addverticelleichboza () 13.adobestiges Nela DOES W17 13. advertise DESVIO) 113. Add Verticalesboa (14) Data.java Vertex Teu Padrages 112.ada) # DataStructures 11at2.addll): 11t2.add(v12) list2.adid (13) # # Datastructures 3 Structures DataStructures. 5 Guess what Gabor 001 Blackjack Paton002 B yte TuanT software citecture Employee Whefactory DTS dts2 = new DTS(); afs2.des 152) Data ) Dis 2 x Orgh 22 b. Graph 2 body.WILD SOCCESUL total Output 9922319 TO ME Type here to search ofte 0 A 64 ENG 11220 @ (b) @ Code the DFS-based algorithm to solve the topological sorting problem for the graphs. You will need to convert the graphs to an adjacency matrix or an adjacency list. Along with the code, you may submit a sheet describing an alternate labeling for the vertices (e.g. instead of a through g, you use 0 through 6). Run the algorithm. If there is no topological sort of the graph (i.e. the graph is not a dag), print a message to that effect. If there is a topological sort, list the order of the vertices that produce a valid topological sort. Note that there may be more than one valid topological sort. If you print out the vertices using the alternate labeling, you will receive full credit. If you use the original labeling (a-g) you will receive a bonus. V
public class Vertex {
private String name;
private boolean visited;
private List adjencyList;
public Vertex(String name){
this.name = name;
this.adjencyList = new ArrayList();
}
public void addVerticesNeighbors(Vertex vertex){
this.adjencyList.add(vertex);
}
public String getName(){
return name;
}
public void setName(String name){
this.name = name;
}
public boolean isVisited(){
return visited;
}
public void setVisited(boolean visited){
this.visited = visited;
}
public List getAdjencyList(){
return adjencyList;
}
public void setAdjencyList(List adjencyList){
this.adjencyList = adjencyList;
}
@Override
public String toString(){
return this.name;
}
}
public class DFS {
private Stack stack;
public DFS(){
this.stack = new Stack();
}
public void dfs(List vertexList){
for(Vertex v : vertexList){
if(!v.isVisited()){
v.setVisited(true);
dfsWithStack(v);
}
}
}
private void dfsWithStack(Vertex rootVertex) {
this.stack.add(rootVertex);
rootVertex.setVisited(true);
while (!stack.isEmpty()) {
Vertex actualVertex = this.stack.pop();
System.out.print(actualVertex + " ");
for (Vertex v : actualVertex.getAdjencyList()) {
if (!v.isVisited()) {
v.setVisited(true);
this.stack.push(v);
}
}
}
}
public class Data {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Vertex v1 = new Vertex("a");
Vertex v2 = new Vertex("b");
Vertex v3 = new Vertex("c");
Vertex v4 = new Vertex("d");
Vertex v5 = new Vertex("e");
Vertex v6 = new Vertex("f");
Vertex v7 = new Vertex("g");
List list = new ArrayList();
v1.addVerticesNeighbors(v2);
v1.addVerticesNeighbors(v3);
v2.addVerticesNeighbors(v7);
v2.addVerticesNeighbors(v5);
v3.addVerticesNeighbors(v6);
v4.addVerticesNeighbors(v1);
v4.addVerticesNeighbors(v2);
v4.addVerticesNeighbors(v3);
v4.addVerticesNeighbors(v6);
v4.addVerticesNeighbors(v7);
v7.addVerticesNeighbors(v6);
v7.addVerticesNeighbors(v5);
list.add(v1);
list.add(v2);
list.add(v3);
list.add(v4);
list.add(v5);
list.add(v6);
list.add(v7);
System.out.println("Graph 1");
DFS dfs = new DFS();
dfs.dfs(list);
System.out.println();
System.out.println("Graph 2");
Vertex v8 = new Vertex("a");
Vertex v9 = new Vertex("b");
Vertex v10 = new Vertex("c");
Vertex v11 = new Vertex("d");
Vertex v12 = new Vertex("e");
Vertex v13 = new Vertex("f");
Vertex v14 = new Vertex("g");
List list2 = new ArrayList();
v8.addVerticesNeighbors(v9);
v9.addVerticesNeighbors(v10);
v10.addVerticesNeighbors(v11);
v11.addVerticesNeighbors(v14);
v14.addVerticesNeighbors(v12);
v12.addVerticesNeighbors(v8);
v13.addVerticesNeighbors(v12);
v13.addVerticesNeighbors(v9);
v13.addVerticesNeighbors(v10);
v13.addVerticesNeighbors(v14);
list2.add(v8);
list2.add(v9);
list2.add(v10);
list2.add(v11);
list2.add(v12);
list2.add(v13);
list2.add(v14);
DFS dfs2 = new DFS();
dfs2.dfs(list2);
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started