Question

create a code in JAVA that takes arguments to do a bfs(breadth first search) or a dfs( depth first search) using a txt file as the graph input.

I have made most of the main function as well as a nose function I just need the bfs and dfs functions to work here's what I have so far, the comments that start with TODO are the parts that I need to finish

Main.java

import java.io.*;
import java.util;
ArrayList; import java.util.Iterator;
import java.util.List;

public class Main {
//class variables
private static boolean extendedOn;
public static String [] arr;
public static List<Node> nodeList;
public static Node firstNode;
public static int vertices;
//main method
public static void main(String[]args){
//the int for the arguments
int argument = 0;
int destination;
extendedOn = false;
boolean isDfs = false;
//checks to make sure that the user specified the destination
if(args[argument].equals("-dest")){
argument++;
try { destination = Integer.parseInt(args[argument]); argument++; }catch (Exception e{
System.out.println("Wrong Argument, needs an integer");
System.exit(0); } }
else{ System.out.println("Please specify the destination using -dest");
System.exit(0); }
//if the first arg is -e if(args[argument].equals("-e")){ argument++; extendedOn = true; }
//if args is dfs if(args[argument].equals("-dfs")){ argument++; isDfs = true; }
//if the args is -bfs else if(args[argument].equals("-bfs")){ argument++; isDfs = false; }
else{
System.out.println("Requires a Search Argument"); System.exit(0); }
//the argument that gets the file
File file = new File( args[argument] ); instantiateList(file); //gets the initial time Long timeStart = System.currentTimeMillis();
//figures out whether to do dfs or bfs
if(isDfs){ DFS(firstNode); }
else{ BFS(); }
//gets the endingTime Long timeEnd = System.currentTimeMillis(); System.out.println("\nTime Taken: " + (timeEnd - timeStart)); }

//method that populates the node list with how many vertices there are
private static void instantiateNodes(){
for(int y = 1; y <= vertices; y++){
nodeList.add(new Node(y)); }
firstNode = nodeList.get(0); }
//method to instantiate the List
public static void instantiateList(File file){
vertices = 0;
//String [] arr; //= new String[0];
//reads the file
try (BufferedReader br = new BufferedReader(new FileReader(file))) {
//gets the vertices then creates the array which the buffered reader will put the values into
vertices = Integer.parseInt(br.readLine());
arr = new String[vertices];
int counter = 0;
//puts the values in String line = null;
while ((line = br.readLine()) != null)
{ arr[counter++] = line; } }
catch (FileNotFoundException e) { e.printStackTrace(); }
catch (IOException e) { e.printStackTrace(); }
//prints out the vertices and initializes the nodeList
System.out.println("\nVertices: " + vertices);
nodeList = new ArrayList<>(); instantiateNodes();
//for loop
for(int x = 0; x < vertices; x++){
//populates a list with the vertexes
String line = arr[x];
List adjacentVertexes = new ArrayList();
//while the line is not empty put it in the list
while(!line.isEmpty())
{ String vertex;
//if there are multiple vertexes
if(line.contains(" "))
{ vertex = line.substring(0, line.indexOf(" "));
//gets the node from the node list and adds it to the Node's adjacency List adjacentVertexes.add(nodeList.get( (Integer.parseInt(vertex)) - 1 )); }
//if there is only one vertex left else{ adjacentVertexes.add(nodeList.get( (Integer.parseInt(line)) - 1 ));
line = ""; break; } //changes the line to the next vertex line = line.substring(line.indexOf(" ")+1); }
//creates the node and initializes it
Node newNode = nodeList.get( ((Node)adjacentVertexes.get(0)).getVertex() - 1 );
//removes the name of the vertex and sets it's list adjacentVertexes.remove(0); newNode.setList(adjacentVertexes);
//adds the newNode to the list of Nodes nodeList.add(newNode); } }
//TODO method for the BFS
public static void BFS(){ System.out.println("BFS:"); }
//TODO method for the DFS
public static void DFS(){ System.out.println("DFS:"); } } }

Node.java

import java.util.List;
public class Node {    
//variable for if the node has been visited before     private boolean hasBeenSearched;   
 private List<Node> adjacency;    
private int vertex;    
public int searched;    
public Node(int v){      
 vertex = v;        
hasBeenSearched = false;     }    
//gets the vertex of the node    
public int getVertex(){        
return vertex;     }    
//sets the variables for if the node has already been searched    
public void setSearch(boolean search){         hasBeenSearched = search;     }    
//gets the varaible for the search of the node     public boolean getSearch(){     
   return hasBeenSearched;     }    
//method used to set the list full of nodes    
public void setList(List<Node> nodeList){         adjacency = nodeList;     }    
//method used to get the Node from the list     public Node getNode(int index){       
  return adjacency.get(index);     }    
//method used to get the size of the adjacency list     public int getSize(){         return adjacency.size();     } }

Answer 1

There are two ways for representing a graph.

1. Using Neighbours list

2. Using Adjacency Matrix

In the methods below we have used Neighbours list approach.

*I would recommend you to use 'Queue' instead of 'List'

BFS:

public static void bfs(Node node)
{
   nodeList.add(node); //to add node in the node list
   node.visited=true;
   while (!nodeList.isEmpty())
   {

       Node element=nodeList.remove(); //to delete the node element
       System.out.print(element.data + "t");
       List<Node> neighbours=element.getNeighbours(); //to get neighbour nodes data
       for (int i = 0; i < neighbours.size(); i++) {
           Node n=neighbours.get(i);
           if(n!=null && !n.visited)
           {
               nodeList.add(n);
               n.visited=true;
           }
       }

   }
}

DFS:

There two ways for implementing DFS:

• Recursive DFS
• Iterative DFS using stack

1. Recursive DFS:

public static void dfs(Node node)

{

System.out.print(node.data + " ");

List<Node> neighbours=node.getNeighbours();

        node.visited=true;

for (int i = 0; i < neighbours.size(); i++) {

Node n=neighbours.get(i);

if(n!=null && !n.visited)

{

dfs(n);

}

}

}

2. Iterative DFS using stack:

public static void dfsUsingStack(Node node)

{

Stack<Node> stack=new  Stack<Node>();

stack.add(node);

while (!stack.isEmpty())

{

Node element=stack.pop();

if(!element.visited)

{

System.out.print(element.data + " ");

element.visited=true;

}

List<Node> neighbours=element.getNeighbours();

for (int i = 0; i < neighbours.size(); i++) {

Node n=neighbours.get(i);

if(n!=null && !n.visited)

{

stack.add(n);

}

}

}

}

Thanks!