求解城市之间的最短总距离是一个非常实际的问题，其大意如下：
某地区由n个城市，如何选择一条路线使各个城市之间的总距离最短？
1.最短总距离算法
先来分析一下上述问题。某个地区的n个城市构成一个交通图，可以使用图结构来描述此问题，其对应关系如下：
- 每个城市代表图中的一个顶点。
- 两个顶点间的边即两个城市之间的路径，边的权值代表了城市间的距离。
这样，求解各个城市之间的最短总距离问题就归结为该图的最小生成树问题。
2.最小生成树算法（prim算法）
//最小生成树算法 static void PrimGraph(GraphMatrix GM){ int i,j,k,min,sum; int[] weight=new int[GraphMatrix.MaxNum]; //权值 char[] vtempx=new char[GraphMatrix.MaxNum]; //临时顶点信息 sum=0; for(i=1;i 0){ //找到具有更小权值的未使用边 min=weight[j]; //保存权值 k=j; //保存邻接点序号 } } sum+=min; //权值累加 System.out.printf("(%c,%c),",vtempx[k],GM.Vertex[k]); //输出生成树一条边 vtempx[k]=USED; //选用 weight[k]=MaxValue; for(j=0;j 3.程序代码示例如下：
package com.cn.datastruct;import java.util.Scanner;//求解城市之间的最短总距离public class Prim { //定义邻接矩阵图结构 static class GraphMatrix{ static final int MaxNum=20; //图的最大顶点数 char[] Vertex=new char[MaxNum]; //保存顶点信息（序号或字母） int GType; //图的类型（0：无向图，1：有向图） int VertexNum; //顶点的数量 int EdgeNum; //边的数量 int[][] EdgeWeight = new int[MaxNum][MaxNum]; //保存边的权 int[] isTrav = new int[MaxNum]; //遍历标志 } static final int MaxValue=65535; //最大值（可设为一个最大整数） static final int USED=0; //已选用顶点 static final int NoL=-1; //非邻接顶点 static Scanner input=new Scanner(System.in); //创建邻接矩阵图 static void CreateGraph(GraphMatrix GM){ int i,j,k; int weight; //权 char EstartV,EendV; //边的起始顶点 System.out.printf("输入图中各顶点信息\n"); for(i=0;i 0){ //找到具有更小权值的未使用边 min=weight[j]; //保存权值 k=j; //保存邻接点序号 } } sum+=min; //权值累加 System.out.printf("(%c,%c),",vtempx[k],GM.Vertex[k]); //输出生成树一条边 vtempx[k]=USED; //选用 weight[k]=MaxValue; for(j=0;j 程序运行结果如下：
寻找最小生成树！请先输入生成图的类型：0输入图的顶点数量：5输入图的边数量：6输入图中各顶点信息第1个顶点：1第2个顶点：2第3个顶点：3第4个顶点：4第5个顶点：5输入构成各边的顶点及权值：第1条边：4 5 2第2条边：3 5 5第3条边：2 4 4第4条边：1 5 3第5条边：1 3 5第6条边：1 2 2最小生成树的边为：(1,2),(1,5),(5,4),(1,3),最小生成树的总权值为：12继续玩吗（y/n）?n游戏结束！