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 是一个布尔数组，它基本上跟踪一个顶点是否已经被推送到队列中。还请记住使用其中一个顶点初始化您的队列。我认为在这种情况下你可以消除递归。

Answer 2

感谢@user98274 我用 bfs() 方法做了一些改变（我认为复杂性方面它是一样的）并且代码看起来像

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

我还在 main() 方法中添加了 q.add(point) 我想要 bfs.

Java 中使用 ArrayList 的 Bfs 实现

Bfs Implementation using ArrayList in Java

java

queue

arraylist

breadth-first-search