这是我从某人那里学到的 prim 算法的代码，http://sourcecodesforfree.blogspot.in/2013/05/10-prims-algorithm.html
这是上一个...我运行了以前的代码，它会给我生成树的最低成本。我想将两个节点之间的权重更改为随机的，同时它是一个完整的加权图。我需要知道我的代码有什么问题..有时当我输入 3 作为节点数时我可以得到正确的结果，在我尝试了几次之后，我发现代码总是添加 w[1][2 ] 与 w[1][3]，然后输出答案。我猜在分配权重时会出现问题。因为前面的代码要求我输入权重以及两个节点之间的权重。
import java.util.*;
import java.io.*;
public class integrated
{
public static Scanner br = new Scanner(System.in);//this is used to listen to any input from the users
static int w [][];//it is the weight between two edges..
static int n;//it is the number of vertices.
//static declaration can be used in every method.
public static void main (String[] args) throws IOException
{
System.out.println("Integrated Algorithm");
System.out.println("\nEnter the number of the vertices: ");
n = br.nextInt();
w = new int[n+1][n+1];
for(int i=1;i<n;i++)
{
for(int j=1;j<=n;j++)
{
if((i!=j)&&(i<j))
{
w[i][j] = w[j][i] = 1+(int)(Math.random()*9);//this step is to give each edge random weight.
}
}
}
System.out.println(n+" by "+n+" Matrix:");
Graph();//it is used to call a new method which can draw a n by n matrix with random weight.
Prim();
}
static void Graph()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
System.out.print(" "+w[i][j]+" ");
}
System.out.println();
}
}
static void Prim()
{
int d[] = new int[n+1];//it is the distance between two nodes.
int total,current,mincost=0;
int visited[] = new int[n+1];//the node which was visited just now.
int near[] = new int[n+1];//the closest node nears to the current node.
for(int i=1;i<=n;i++)
{
near[i]=visited[i]=0;
}
for(int i=1;i<=n;i++)
{
d[i]=32767;//initiate the distance between two nodes as 32767, but its not the real distance between two nodes in matrix.
}
current = 1;//initiate the first and starting node as 1.
visited[current]=1;//and initiate the visited[current] equal to 1.
d[current]=0;
total=1;//this is just a number, which is used to do the iterations.
System.out.println("Minimum Spanning Tree: ");
while(total!=n)
{
for(int i=1;i<=n;i++)
{
if(w[i][current]!=0&&visited[i]!=1)//if we want to keep moving, we have to meet the conditions, here weight of current and nodes is not equal to zero and ignore the current node to make the comparisons.
if(w[i][current]<d[i])//and weight of i and current nodes have to be less than d[i], which is initiated by me before.
{
d[i]=w[i][current];//if it passed the 'if', then d[i] would be covered by the shortest edge, which the starting node was current.
near[i]=current;
}
}
int min=32767;//
for(int i=1;i<=n;i++)
{
if(visited[i]!=1&&d[i]<mincost)
{
min=d[i];
current=i;//after the comparisons, they select the closest node to cover the current.
System.out.println(near[i]+" to "+current);
}
}
visited[current]=1;//after each iteration, the current changes as well, so the visited[current] should be changed as the changes of current.
total++;//after all the steps has been finished in one iteration, total is increased by one.
}
for(int i=1;i<=n;i++)
mincost+=d[i];
System.out.println("minimum cost= "+mincost);
}
}