-4

我在编码以获得最小生成树时遇到了一些异常问题。

错误消息类似于：线程“main”中的异常 java.lang.ArrayIndexOutOfBoundsException: 1 at Assignment.RandomGraph.main(RandomGraph.java:36)

import java.util.*;
public class RandomGraph
{
public static Scanner br = new Scanner(System.in);
static int w [][];//it represents the weight between every two nodes.
static int n;//number of the vertices that you typed.
static int i, j;
static int visited[] = new int[n];
static int next[] = new int[n];
static int d[]=new int[n];



public static void main (String[] args)
{
    System.out.println("Find the shortest edge");
    System.out.println("\nEnter the number of the vertices: ");
    n = br.nextInt();
    w = new int[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            if((i!=j))
            {
            w[i][j] = w[j][i]= 1+(int)(Math.random()*9);
            }
            else if(i == j)
            {
                w[i][j] = w[j][i] = 0;
            }
        }
    for(i=1;i<=n;i++)
    {
        next[i]=visited[i]=0;
        d[i]=32767;
    }
    Graph();
    Prim();
}

static void Graph()
{
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            System.out.print("  "+w[i][j]+"  ");
        }
    System.out.println();
    }
}

static void Prim()
{
    int current=1;
    int total=1;
    int mincost;

    d[current]=0;
    visited[current]=1;
    do{
        for(i=1;i<=n;i++)
        {
            if((w[current][i]!=0)&&(visited[i]==0)&&(w[current][i]<d[i]))
            {
                d[i]=w[current][i];
                next[i]=current;
            }
        }
        mincost = 32767;
        for(i=1;i<=n;i++)
        {
            if((visited[i]==0)&&d[i]<mincost)
            {
                mincost=d[i];
                current=i;
            }
        }
        visited[current]=1;
        total++;
    }while(total!=n);

    mincost=0;
    for(i=1;i<=n;i++)
    {
        mincost=mincost+d[i];
        System.out.print("\n Minimum cost = "+mincost);
        System.out.print("\n Minimum Spanning tree is ");
    }
    for(i=1;i<=n;i++)
    {
        System.out.print("\n"+i+" to "+next[i]);
    }
}

}

4

3 回答 3

2

好吧，你的 fors 中的变量 i 应该从 0 到 n，完全是

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

如果将数组/矩阵声明为数组[n]，系统将创建一个大小为 n 的数组，但从 0 开始，而不是 1

如，array[0] = first element NOT array[1]

=> 最后一个元素 =array[n-1]

于 2013-08-03T18:20:03.753 回答
0

你有数组：w [][], visited[], next[], d[]. 都有n元素。您可以使用来自 的索引来访问它们0 - (n-1)。

main 方法（最后一个）下面的循环和里面的所有循环static void Prim()都会抛出错误，因为你有i <= n. 您正在尝试访问n index不存在的

for(i=1;i<=n;i++) {
    next[i]=visited[i]=0;
    d[i]=32767;
}
于 2013-08-03T19:12:39.907 回答
0

因为您的 next[] 数组的大小为 0，并且您尝试使用索引 1 获取 elemetti。

读这个：

http://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html

于 2013-08-03T18:26:08.747 回答