我正在尝试进行 BFS 搜索但得到运行时错误索引超出范围异常

Question

给定一个有向图，任务是从 0 开始对该图进行广度优先遍历。

完成函数 bfsOfGraph() 到 return 给定图的广度优先遍历。

这里，V表示顶点数

问题来了link

class Solution
{    
         public ArrayList<Integer> bfsOfGraph(int V , ArrayList<ArrayList<Integer>> adj)
         {    
                  ArrayList<Integer> bfs = new ArrayList<>();
                  boolean vis[] = new boolean[V+1]; 
        
                 for( int i = 1; i < V+1 ; i++){
                         if(vis[i] == false){
                             Queue<Integer> q = new LinkedList<>();
                             q.add(i);
                             vis[i] = true;
                
                             while(!q.isEmpty()){
                                 
                                     Integer node = q.poll();
                   
                                     bfs.add(node);
                 
                                    for(Integer it : adj.get(node)){
                                            if(vis[it] == false){
                                            vis[it] = true;
                                            q.add(it);
                                   }
                            }   
                      }
                }
          }
        return bfs;
        
    }
}

Answer 1

当你知道你已经从 0 开始（图的原点）时，为什么要调用图的每个节点（顶点）。我认为你误解了这些问题。您必须在 Origin 0 上应用 BFS。您也可能会遇到 IndexOutOfBound 异常，因为图形的所有顶点都从 0 到 V-1（含）。我可以看到您将图形顶点视为 1 到 V（含）。

public ArrayList<Integer> bfsOfGraph(int V,ArrayList<ArrayList<Integer>> adj)
    {
        Queue<Integer> queue = new LinkedList<>();
        boolean visited[] = new boolean[V];
        ArrayList<Integer> results = new ArrayList<>();
        queue.add(0);
        while(!queue.isEmpty()){
            Integer nextNode = queue.poll();
            results.add(nextNode);
            visited[nextNode] = true;
            if(adj.get(nextNode) != null){
                for(int neighbor : adj.get(nextNode)){
                    if(!visited[neighbor]){
                        queue.add(neighbor);
                        visited[neighbor] = true;
                    }
                }
            }
        }
        return results;
    }

我正在尝试进行 BFS 搜索但得到运行时错误索引超出范围异常

I am trying to do BFS search but get Runtime Error Index out Of Bounds Exception

java

graph

breadth-first-search

indexoutofboundsexception