赞
踩
目录
最小生成树:带权连通图的生成树中 边的权值之和最小的那个生成树。
- 最小生成树不是唯一的。当图中的各边权值互不相等时,最小生成树是唯一的;
- 若无向连通图本身是一棵树时(边数比顶点数少1 ),则最小生成树就是它本身。
- 最小生成树的边数为顶点数减1
(找距离最近的结点)
- void Prim (G , T ) {
- T = 空集 ; //初始化空树
- U={w}; //添加任一顶点w
- while( (V-U) != 空集 ) { //若树中不含全部顶点
- 设 ( u , v ) 是使u∈U 与 v∈(V-U),且权值最小的边;
- T=TU{ (u,v) }; //边归入树
- U=U U{v); //顶点归入树
- }
- }
题目背景:Farmer John 被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。
题目描述:FJ 已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。为了用最小的消费,他想铺设最短的光纤去连接所有的农场。
你将得到一份各农场之间连接费用的列表,你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过。
(采用基本Prim算法求解:Kruskal算法求解见专栏)
- public class MST {
- public int prim(int[][] w){
- int n=w.length;
- //最小生成树总权值
- int result=0;
- //加入的顶点集
- boolean[] Vex=new boolean[n];
- //当前已确定的顶点集到i的最短距离
- int[] dis=new int[n];
-
- //初始化
- //任选v点开始点
- int v=0;
- Vex[0]=true;
- for (int i = 0; i < n; i++) {
- dis[i]=w[v][i];
- }
-
- //遍历n次,选n个顶点
- for (int l = 0; l < n; l++) {
- //选取当前顶点集到其它顶点的最短路径
- int temp=-1;
- for (int i = 0; i < n; i++) {
- if ((!Vex[i])&&(temp==-1||(dis[i]>0&&dis[i]<dis[temp]))){
- temp=i;
- }
- }
- if (temp==-1) {
- return -1;
- }
- //将找到的距离最近的顶点加入顶点集
- Vex[temp] = true;
- v = temp;
- result += dis[temp];
-
- //由于顶点集新加入一个顶点,要更新当前已确定的顶点集到i的最短距离
- for (int i = 0; i < w.length; i++) {
- if ((!Vex[i])&&w[v][i]>0&&w[v][i]<dis[i]){
- dis[i]=w[v][i];
- }
- }
- }
- return result;
- }
- public static void main(String[] args) {
- Scanner scan=new Scanner(System.in);
- int n=scan.nextInt();
- int[][] w=new int[n][n];
- for (int i = 0; i < w.length; i++) {
- for (int j = 0; j < w.length; j++) {
- w[i][j]=scan.nextInt();
- }
- }
- System.out.println(new MST().prim(w));
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。