CODEWITHSUNDEEP
javaarraylistqueuebreadth-first-search
Nikhil Pathania
Nikhil Pathania

Reputation: 821

Bfs Implementation using ArrayList in Java

I have written code for bfs implementation using java, and i wanted help regarding optimization of this code:

 package graphs;

 import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.io.PrintWriter;
 import static java.lang.System.out;
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.Queue;
 import java.util.StringTokenizer;


 public class Bfs {

static ArrayList<ArrayList<Integer>> a;
static boolean visited[];
static Queue q=new LinkedList<Integer>();
public static void main(String args[]) throws IOException
{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    PrintWriter w = new PrintWriter(System.out);
    out.println("Enter the vertice and edge");
    StringTokenizer st=new StringTokenizer(br.readLine());
    int vertice,edge;

    vertice=ip(st.nextToken());
    edge=ip(st.nextToken());
    a=new ArrayList<ArrayList<Integer>>(vertice);
    for(int i=0;i<vertice;i++)
    {
        a.add(new ArrayList<Integer>());
    }
    out.println("Enter all the points X Y");
    int n=vertice;
    while(n-->0)
    {
        st=new StringTokenizer(br.readLine());
        graph(ip(st.nextToken()),ip(st.nextToken()));

    }
    visited=new boolean[vertice];
    out.println("Enter any vertice number");
    bfs(ip(br.readLine()));

   // w.println(a);
    w.close();
}

public static void graph(int p1,int p2)
{
    a.get(p1).add(p2);
    a.get(p2).add(p1);
}

public static void bfs(int vertice)
{
    if(!visited[vertice])
    {
        visited[vertice]=true;
        q.add(vertice);
    }
    Iterator it=a.get(vertice).iterator();

    while(it.hasNext())
    {
        int currver=(int)it.next();
      // System.out.println(visited[currver]+" :"+currver);

        if(!visited[currver])
        {
            q.add(currver);
            visited[currver]=true;
        }
    }
//   System.out.println(q); 
    System.out.println(q.poll());
    if(!q.isEmpty())
    {
        bfs((int)q.peek());
    }
}
   public static int ip(String s){
    return Integer.parseInt(s);
}
}

Actually i am calling bfs using recursion and wanted to remove it, so it would be a help if you can remove that recursive call.

Upvotes: 0

Views: 4106

Answers (2)

Nikhil Pathania
Nikhil Pathania

Reputation: 821

Thanks @user98274 i made some changes with bfs() method (i think complexity wise it will be same) and code looks like

 public static void bfs(){

     while(!q.isEmpty()){
       int v = (int)q.poll();
       System.out.println(v);
       visited[v]=true;
       Iterator it = a.get(v).iterator();

       while(it.hasNext()){
         int vert = (int)it.next();
         if(!visited[vert]){
           q.add(vert);
           visited[vert]=true;
         }
       } 
    }
 }

Also in main() method i added q.add(point) for which i wanted bfs.

Upvotes: 0

Kushal Sharma
Kushal Sharma

Reputation: 186

public static void bfs(){
while(!q.empty()){
  int v = q.poll();
  System.out.println(v);
  visited[v]=true;
  Iterator it = a.get(v);
  while(it.hasNext()){
    int vert = (int)it.next();
    if(!pushed[vert]){
        q.add(vert);
        pushed[vert]=true;
    }
  } 
 }
}

Here pushed is a boolean array that basically keeps track of whether a vertex has been pushed to the queue or not. Also remember to initialize your queue with one of the vertices. I think in such a case you can eliminate the recursion.

Upvotes: 1

Related Questions