Java program please explain code and add a lot of comments Functional Requiremen

Question

Java program please explain code and add a lot of comments

Functional Requirements Write a Javs program (based on a graph traversal algorithm you've learned in this class) that, for a given undirected graph, outputs: (E) vertices of each connected component; (ii) a cycle or a message that the graph is acyclic (if there are more than one cycles in a grsph you are required to output just one of them) Your programs should take inputs from a file via the command line with the following structure in the input file. Each line of the input file represents a graph. The first number in a line species the number of vertices in the graph. Then pairs of vertices define the edges. An example of an input file is as follows: 5 (12) (3,4) (3,5) (4,5) It specifies two graphs. The first graph has five vertices1,2,3,4,5) and four edges. The Proper output should look (something) like: second graph has four vertices (1,2,3,4) and three edges. Graphl: Two connected components: (1 2) 3 45 Cycle detected: 3-4-5-3 One connected component: 11 2 3 4) The graph is acyclic. You must test your programs on a nontrivial input file (with at least 3 graphs and each graph having 7-10 nodes). For the second problem, your test graphs should cover both cyclic and acyclic graphs. Your output should be formatted nicely so that it is easy to read. Additional Requirements Additionally, you should create the following ordinary text file: README: Information on how to compile and run your program.

Explanation / Answer

import java.io.*;

import java.util.*;

//Class Graph definition

class Graph

{

// Number of vertices

private int V;

// Adjacency List

private LinkedList<Integer> adj[];

// Parameterized constructor

Graph(int v)

{

// Assign vertices

V = v;

// Creates list based on vertices

adj = new LinkedList[v];

// Loops till end of vertices and allocates memory

for(int i=0; i<v; ++i)

adj[i] = new LinkedList();

}// End of constructor

// Method to add an edge into the graph

void addEdge(int v,int w)

{

adj[v].add(w);

adj[w].add(v);

}// End of method

// Method that uses visited[] and parent to detect cycle in subgraph reachable from vertex v

Boolean isCyclicUtil(int ve, Boolean visited[], int parent)

{

// Mark the current node as visited

visited[ve] = true;

Integer co;

// Recur for all the vertices adjacent to this vertex

Iterator<Integer> it = adj[ve].iterator();

// Checks for value availability

while (it.hasNext())

{

// Extracts data

co = it.next();

// If an adjacent is not visited, then recur for that adjacent

if (!visited[co])

{

// Calls the method to check cycle

if (isCyclicUtil(co, visited, ve))

return true;

}// End of if

// If an adjacent is visited and not parent of current vertex, then there is a cycle.

else if (co != parent)

return true;

}// End of while

return false;

}// End of method

// Method to return true if the graph contains a cycle, else false.

Boolean isCyclic()

{

// Mark all the vertices as not visited and not part of recursion stack

Boolean visited[] = new Boolean[V];

// Loops till end of vertices

for (int c = 0; c < V; c++)

visited[c] = false;

// Call the recursive helper function to detect cycle in different Depth First Search trees

for (int c = 0; c < V; c++)

// Don't recur for u if already visited

if (!visited[c])

// Calls the method to check cycle

if (isCyclicUtil(c, visited, -1))

return true;

return false;

}// End of method

  

// main method definition

public static void main(String ss[])throws FileNotFoundException

{

// To store vertices and edges

int no, e1, e2;

// Creating File instance to reference text file in Java

File text = new File("GraphEdges.txt");

// Creating Scanner instance to read File in Java

Scanner scnr = new Scanner(text);

// Reading number of edges for first graph

no = scnr.nextInt();

// Displays edges

System.out.println("Edges = " + no);

// Create a graph as extracted number of edges

Graph g1 = new Graph(no);

// Loops till end of vertices

for(int x = 0; x < no-1; x++)

{

// Extracts vertices

e1 = scnr.nextInt()-1;

e2 = scnr.nextInt()-1;

// Displays vertices

System.out.println("Vertiex1 = " + (e1+1) + " Vertiex2 = " + (e2+1));

// Adds vertices to graph one

g1.addEdge(e1, e2);

}// End of for loop

// Checks for cycle

if (g1.isCyclic())

System.out.println("Graph contains cycle");

else

System.out.println("Graph doesn't contains cycle");

  

// Reading number of edges for second graph

no = scnr.nextInt();

// Displays edges

System.out.println("Edges = " + no);

// Create a graph as extracted number of edges

Graph g2 = new Graph(no);

// Loops till end of vertices   

for(int x = 0; x < no-1; x++)

{

// Extracts vertices

e1 = scnr.nextInt()-1;

e2 = scnr.nextInt()-1;

// Displays vertices

System.out.println("Vertiex1 = " + (e1+1) + " Vertiex2 = " + (e2+1));

// Adds vertices to graph two

g2.addEdge(e1, e2);

}// End of for loop

// Checks for cycle   

if (g2.isCyclic())

System.out.println("Graph contains cycle");

else

System.out.println("Graph doesn't contains cycle");   

}// End of main method

}// End of class

Sample Run:

Edges = 5

Vertiex1 = 1 Vertiex2 = 2

Vertiex1 = 3 Vertiex2 = 4

Vertiex1 = 3 Vertiex2 = 5

Vertiex1 = 4 Vertiex2 = 5

Graph contains cycle

Edges = 4

Vertiex1 = 1 Vertiex2 = 2

Vertiex1 = 2 Vertiex2 = 3

Vertiex1 = 1 Vertiex2 = 4

Graph doesn't contains cycle

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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