DAG的索引越界错误

Question

我正在编写一个程序，用标准中的输入为DAG找到最长的路径。我终于编译了它，它说由于我的数组列表，它使用了未检查或不安全的操作，但我得到了一个索引越界错误，感觉我已经尝试更改了每个循环，我一定错过了一些东西，感谢高级提示。这是我的代码：

    import java.io.*;
    import java.util.*;
public class countLongPaths
{
static final int NINF = Integer.MIN_VALUE;
public class AdjListNode
{
    private int v;
    private int weight;
    AdjListNode(int inV, int inW) 
        { 
            v = inV;  
            weight = inW; 
        }
    int getV() 
        { 
            return v; 
        }
    int getWeight()  
        { 
            return weight; 
        }
}//end of adj list class
public class Graph
    {
        private int V;
        private LinkedList<AdjListNode>adj[];
        //set up graph with given number of verticies
        Graph(int v)
        {
            V=v;
            adj = new LinkedList[V];
            for (int i = 0; i < v; ++i)
                adj[i] = new LinkedList<AdjListNode>();
        }
        //function to add edges to graph
        void addEdge(int u, int v, int weight)
        {
            AdjListNode node = new AdjListNode(v,weight);
            adj[u].add(node);// Add v to u's list
        }
        //function to set order to go through vertices
        void setOrder(int v, Boolean visited[], Stack stack)
        {
            //Set node to visited when on it
            visited[v] = true;
            Integer i;
            //for all nodes connected to current repeat
            Iterator<AdjListNode> it = adj[v].iterator();
            while (it.hasNext())
            {
                AdjListNode node =it.next();
                if (!visited[node.getV()])
                    setOrder(node.getV(), visited, stack);
            }
            //Once done with current add it to the stack
            stack.push(new Integer(v));
        }
        //function to find longest paths from s
        int longestPath()
        {
            Stack stack = new Stack();
            int LP[] = new int[V];
            //set all vertices to unvisited
            Boolean visited[] = new Boolean[V];
            for(int i = 1; i <= V; i++)
                visited[i] = false;
            //call set order function from each vertex
            for (int i = 1; i <= V; i++)
            {
                if(visited[i] == false)
                    setOrder(i, visited, stack);
            }
            //initialize distaces to all verices as negative infinity
            //set distace to source to 0
            LP[1] = 0;
            for(int i = 2; i <= V; i++)
                LP[i] = NINF;
            //go through vertices in order
            while(stack.empty() == false)
                {
                    int u = (int)stack.pop();
                    //update LP for adj vertices
                    Iterator<AdjListNode> it;
                    if (LP[u] != NINF)
                    {
                        it = adj[u].iterator();
                        while (it.hasNext())
                        {
                            AdjListNode i = it.next();
                            if(LP[i.getV()] < LP[u] + i.getWeight())
                                LP[i.getV()] = LP[u] + i.getWeight();
                        }
                    }
                }
                return LP[V];
        }
    }//end of graph class
    //Method to make a new graph
    public Graph newGraph(int number)
    {
        return new Graph(number);
    }
public static void main(String[]args)
{
    countLongPaths n = new countLongPaths();
    int GN = 0;
    int count = 1;
    Scanner scan = new Scanner(System.in);
    GN = scan.nextInt();
    while (count<= GN)
    {
        int N = 0;// nodes
        int M = 0;//edges
        N = scan.nextInt();
        M = scan.nextInt();
        //setup a new graph
        Graph g = n.newGraph(N);
        //set edges for new graph
        for(int i = 1; i <= M; i ++)
        {
            int I = scan.nextInt();
            int J = scan.nextInt();
            int W = scan.nextInt();
            g.addEdge(I, J, W);
        }
        int dist = 0;
        dist = g.longestPath();
        System.out.println("graph number: " + count);
        System.out.println("longest path: " + dist);
        System.out.println("number of longest paths: ");
        System.out.println();
        count++;
    }//end of while
}//end main
}//end program

编辑1对于当前代码，这是错误：

  Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
at countLongPaths$Graph.<init>(countLongPaths.java:36)
at countLongPaths.newGraph(countLongPaths.java:108)
at countLongPaths.main(countLongPaths.java:127)

Answer 1

正如堆栈跟踪所说，异常发生在Graph类构造函数中。

更具体地说，它发生在循环中唯一的一行：

adj = new LinkedList[V];
for (int i = 0; i <= v; ++i)
    adj[i] = new LinkedList<AdjListNode>();

假设您的意思是小写v和大写V都是同一个变量，那么您定义了一个大小为V的数组，该数组从0索引到V-1，但您正在从0运行到V（您的条件是i <= V），这就是为什么您得到IndexOutOfBoundsException的原因。

只需更改循环的条件（删除=）：

for (int i = 0; i < v; ++i)