java - Java中使用ArrayList实现Bfs

Question

我已经使用 java 编写了 bfs 实现的代码，并且我需要有关优化此代码的帮助:

 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);
}
}

实际上，我正在使用递归调用 bfs，并希望将其删除，因此如果您可以删除该递归调用，将会有所帮助。

Answer 1

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;
    }
  } 
 }
}

这里的 Pushed 是一个 boolean 数组，它基本上跟踪顶点是否已被推送到队列中。还要记住用顶点之一初始化队列。我认为在这种情况下你可以消除递归。