Java基础实践：自考操作04748——最小生成树与Prim算法

《Java语言程序设计（一）实践操作04748》：

1、用java语言编写一个java应用程序根据给定图实现最小生成树(Minimal Spinning Tree),可以采用Prim算法和Kruskal算法，并用动画的方式表示最小生成树的生成过程。

2、编写一个java程序实现Min堆(Heap)或者Max堆的主要功能，并用动画的方式表示Min堆或者Max堆的变化过程。

3、编写一个求解图的最小周游路径的算法，并用动画的方式表示最小周游路径的生成过程。路径的生成过程。

答：第一题：

importjava.util.*;

publicclass Main { 

static intMAXCOST=Integer.MAX_VALUE;

static int Prim(intgraph[][], int n){      /* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */ 

int lowcost[]=newint[n+1];        /* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */

int mst[]=newint[n+1];

int min, minid, sum= 0;               /* 默认选择1号节点加入生成树，从2号节点开始初始化 */ 

for (int i = 2; i<= n; i++){               /* 最短距离初始化为其他节点到1号节点的距离 */

             lowcost[i]= graph[1][i];             /* 标记所有节点的起点皆为默认的1号节点 */

             mst[i]= 1; }                                   /* 标记1号节点加入生成树 */ 

mst[1] = 0;                                           /* n个节点至少需要n-1条边构成最小生成树 */

for (int i = 2; i<= n; i++){

 min = MAXCOST; minid = 0;      /* 找满足条件的最小权值边的节点minid */

for (int j = 2; j<= n; j++){            /* 边权值较小且不在生成树中 */ 

if (lowcost[j] <min && lowcost[j] != 0)

{ min = lowcost[j];

minid = j; 

} 

}                                 /* 输出生成树边的信息:起点，终点，权值 */ 

System.out.printf("%c- %c : %d\n", mst[minid] + 'A' - 1, minid + 'A' - 1, min); /* 累加权值 */ 

sum += min;             /* 标记节点minid加入生成树 */

lowcost[minid] = 0;       /* 更新当前节点minid到其他节点的权值 */ 

for (int j = 2; j<= n; j++){     /* 发现更小的权值 */

 if (graph[minid][j] < lowcost[j]){      /* 更新权值信息 */ 

lowcost[j] =graph[minid][j]; /* 更新最小权值边的起点 */