JAVA HELP PLEASE JAVA PROGRAM Make a program on a graph traversal algorithm eith
ID: 3601328 • Letter: J
Question
JAVA HELP PLEASE
JAVA PROGRAM
Make a program on a graph traversal algorithm either Depth-first search (DFS) or Breadth-first search (BFS) for a given undirected graph, outputs: (i) 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 graph, you are required to output just one of them).
The 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 the rest of the numbers in the brackets represent the edages.
THIS IS AN EXAMPLE OF AN INPUT FILE:
5 (1,2) (3,4) (3,5) (4,5)
4 (1,2) (2,3) (1,4)
It specifies two graphs. The first graph has five vertices (1,2,3,4,5) and four edges. The second graph has four vertices (1,2,3,4) and three edges.
OUTPUT SHOULD LOOK LIKE:
Graph1:
Two connected components: {1 2} {3 4 5}
Cycle detected: 3 - 4 - 5 - 3
Graph2:
One connected component: {1 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.
EXTRA HELP: Connected component: in graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
PLEASE HELP I NEED IT ASAP
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 ve
Boolean isCyclicHelper(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 (isCyclicHelper(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 and set all the nodes visited to false
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 (isCyclicHelper(c, visited, -1))
return true;
return false;
}// End of method
// Method to print connected components in an undirected graph
void connectedComponents()
{
// Mark all the vertices as not visited
Boolean visited[] = new Boolean[V];
// Loops till end of vertices and set all the nodes visited to false
for(int c = 0; c < V; c++)
visited[c] = false;
System.out.print(" Connected components: ");
// Loops till end of vertices
for (int c = 0; c < V; c++)
{
// Checks if the current index position value of visited array is false
if (visited[c] == false)
{
// Print all reachable vertices from v
System.out.print("{");
DFSHelper(c, visited);
System.out.print("}");
}// End of if condition
}// End of for loop
}// End of method
// Method to display the connected components
void DFSHelper(int v, Boolean visited[])
{
int no;
// Mark the current node as visited and print it
visited[v] = true;
System.out.print((v+1) + " ");
// Recursion for all the vertices adjacent to this vertex
Iterator<Integer> i = adj[v].iterator();
// Loops till data is available in adj array
while (i.hasNext())
{
// Extracts data and stores it in n
no = i.next();
// Checks whether visited array no index position contains not true
if (!visited[no])
// Recursively call the function DFSHelper()
DFSHelper(no, visited);
}// End of while loop
}// 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
// Calls the method to display connected components
g1.connectedComponents();
// Checks for cycle
if (g1.isCyclic())
System.out.println(" Graph contains cycle");
else
System.out.println(" The graph is acyclic.");
// 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
// Calls the method to display connected components
g2.connectedComponents();
// Checks for cycle
if (g2.isCyclic())
System.out.println(" Graph contains cycle");
else
System.out.println(" The graph is acyclic.");
}// 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
Connected components: {1 2 }{3 4 5 }
Graph contains cycle
Edges = 4
Vertiex1 = 1 Vertiex2 = 2
Vertiex1 = 2 Vertiex2 = 3
Vertiex1 = 1 Vertiex2 = 4
Connected components: {1 2 3 4 }
The graph is acyclic.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.