首页 / 算法 / 城市之间的最短总距离（最小生成树算法）
城市之间的最短总距离（最小生成树算法）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了城市之间的最短总距离（最小生成树算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4509字，纯文字阅读大概需要7分钟。
内容图文
求解城市之间的最短总距离是一个非常实际的问题，其大意如下：
某地区由n个城市，如何选择一条路线使各个城市之间的总距离最短？
1.最短总距离算法
先来分析一下上述问题。某个地区的n个城市构成一个交通图，可以使用图结构来描述此问题，其对应关系如下：
- 每个城市代表图中的一个顶点。
- 两个顶点间的边即两个城市之间的路径，边的权值代表了城市间的距离。
这样，求解各个城市之间的最短总距离问题就归结为该图的最小生成树问题。
2.最小生成树算法（prim算法）
//
最小生成树算法
static
void
PrimGraph(GraphMatrix GM){
int
i,j,k,min,sum;
int[] weight=newint[GraphMatrix.MaxNum]; //权值char[] vtempx=newchar[GraphMatrix.MaxNum]; //临时顶点信息
sum=0;
for(i=1;i<GM.VertexNum;i++){ //保存邻接矩阵中的一行数据
weight[i]=GM.EdgeWeight[0][i];
if(weight[i]==MaxValue){
vtempx[i]=(char) NoL;
}else{
vtempx[i]=GM.Vertex[0]; //邻接顶点 }
}
vtempx[0]=USED; //选用
weight[0]=MaxValue;
for(i=1;i<GM.VertexNum;i++){
min=weight[0]; //最小权值
k=i;
for(j=1;j<GM.VertexNum;j++){
if(weight[j]<min&&vtempx[j]>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<GM.VertexNum;j++){ //重新选择最小边if(GM.EdgeWeight[k][j]<weight[j]&&vtempx[j]!=0){
weight[j]=GM.EdgeWeight[k][j]; //权值
vtempx[j]=GM.Vertex[k];
}
}
}
System.out.printf("\n最小生成树的总权值为：%d\n", sum);
}
3.程序代码示例如下：
package
com.cn.datastruct;
import
java.util.Scanner;
//
求解城市之间的最短总距离
public
class
Prim {
//
定义邻接矩阵图结构
static
class
GraphMatrix{
static
final
int MaxNum=20; //图的最大顶点数char[] Vertex=newchar[MaxNum]; //保存顶点信息（序号或字母）int GType; //图的类型（0：无向图，1：有向图）int VertexNum; //顶点的数量int EdgeNum; //边的数量int[][] EdgeWeight = newint[MaxNum][MaxNum]; //保存边的权int[] isTrav = newint[MaxNum]; //遍历标志 }
staticfinalint MaxValue=65535; //最大值（可设为一个最大整数）staticfinalint USED=0; //已选用顶点staticfinalint NoL=-1; //非邻接顶点static Scanner input=new Scanner(System.in);
//创建邻接矩阵图staticvoid CreateGraph(GraphMatrix GM){
int i,j,k;
int weight; //权char EstartV,EendV; //边的起始顶点
System.out.printf("输入图中各顶点信息\n");
for(i=0;i<GM.VertexNum;i++){ //输入顶点
System.out.printf("第%d个顶点：", i+1);
GM.Vertex[i]=(input.next().toCharArray())[0]; //保存到各顶点的数组元素中 }
System.out.printf("输入构成各边的顶点及权值：\n");
for(k=0;k<GM.EdgeNum;k++){ //输入边的信息
System.out.printf("第%d条边：", k+1);
EstartV=input.next().charAt(0);
EendV=input.next().charAt(0);
weight=input.nextInt();
for(i=0;EstartV!=GM.Vertex[i];i++); //在已有顶点中查找始点for(j=0;EendV!=GM.Vertex[j];j++); //在已有的顶点中查找终点
GM.EdgeWeight[i][j]=weight; //对应位置保存权值，表示有一条边if(GM.GType==0){ //若是无向图
GM.EdgeWeight[j][i]=weight;
}
}
}
//清空矩阵staticvoid ClearGraph(GraphMatrix GM){
int i,j;
for(i=0;i<GM.VertexNum;i++){
for(j=0;j<GM.VertexNum;j++){
GM.EdgeWeight[i][j]=MaxValue; //设置矩阵中各元素的值为MaxValue }
}
}
//输出邻接矩阵staticvoid OutGraph(GraphMatrix GM){
int i,j;
for(j=0;j<GM.VertexNum;j++){
System.out.printf("\t%c", GM.Vertex[j]); //在第一行输出顶点信息 }
System.out.println();
for(i=0;i<GM.VertexNum;i++){
System.out.printf("%c", GM.Vertex[i]);
for(j=0;j<GM.VertexNum;j++){
if(GM.EdgeWeight[i][j]==MaxValue){ //若权值为最大值
System.out.printf("\tZ"); //以Z表示无穷大
}else{
System.out.printf("\t%d", GM.EdgeWeight[i][j]); //输出边的权值 }
}
System.out.println();
}
}
//最小生成树算法staticvoid PrimGraph(GraphMatrix GM){
int i,j,k,min,sum;
int[] weight=newint[GraphMatrix.MaxNum]; //权值char[] vtempx=newchar[GraphMatrix.MaxNum]; //临时顶点信息
sum=0;
for(i=1;i<GM.VertexNum;i++){ //保存邻接矩阵中的一行数据
weight[i]=GM.EdgeWeight[0][i];
if(weight[i]==MaxValue){
vtempx[i]=(char) NoL;
}else{
vtempx[i]=GM.Vertex[0]; //邻接顶点 }
}
vtempx[0]=USED; //选用
weight[0]=MaxValue;
for(i=1;i<GM.VertexNum;i++){
min=weight[0]; //最小权值
k=i;
for(j=1;j<GM.VertexNum;j++){
if(weight[j]<min&&vtempx[j]>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<GM.VertexNum;j++){ //重新选择最小边if(GM.EdgeWeight[k][j]<weight[j]&&vtempx[j]!=0){
weight[j]=GM.EdgeWeight[k][j]; //权值
vtempx[j]=GM.Vertex[k];
}
}
}
System.out.printf("\n最小生成树的总权值为：%d\n", sum);
}
publicstaticvoid main(String[] args) {
GraphMatrix GM=new GraphMatrix(); //定义保存邻接表结构的图char again;
String go;
System.out.println("寻找最小生成树！");
do{
System.out.print("请先输入生成图的类型：");
GM.GType=input.nextInt(); //图的种类
System.out.print("输入图的顶点数量：");
GM.VertexNum=input.nextInt(); //输入图的顶点数
System.out.print("输入图的边数量：");
GM.EdgeNum=input.nextInt(); //输入图边数
ClearGraph(GM); //清空图
CreateGraph(GM); //生成邻接表结构的图
System.out.print("最小生成树的边为：");
PrimGraph(GM);
System.out.println("\n继续玩吗（y/n）?");
go=input.next();
}while(go.equalsIgnoreCase("y"));
System.out.println("游戏结束！");
}
}
原文：http://www.cnblogs.com/gaopeng527/p/4506887.html
内容总结
以上是互联网集市为您收集整理的城市之间的最短总距离（最小生成树算法）全部内容，希望文章能够帮你解决城市之间的最短总距离（最小生成树算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】