1：通过计算权值最小的连接线，
在边赋权图中，权值总和最小的生成树称为最小生成树。构造最小生成树有两种算法，分别是prim算法和kruskal算法。在边赋权图中，如下图所示:
在上述赋权图中，可以看到图的顶点编号和顶点之间邻接边的权值，若要以上图来构建最小生成树。结果应该如下所示:
这样构建的最小生成树的权值总和最小，为17
在构建最小生成树中，一般有两种算法，prim算法和kruskal算法
在prim算法中，通过加入最小邻接边的方法来建立最小生成树算法。首先构造一个零图，在选一个初始顶点加入到新集合中，然后分别在原先的顶点集合中抽取一个顶点，使得构成的边为权值最小，然后将该笔边加入到图中，并将抽出的顶点加入到新集合中，重复这个过程，知道新集合等于原先的集合。
代码如下:
package com.qdcz.breadth.demo;
import java.util.ArrayList;
import java.util.List;;
/**
*
* <p>Title: MinimumTreeA</p>
* <p>Description:最小树实现类</br>
* 最小生成树prim算法，加入最小邻接边生成最小生成树。</br>
* 首先构造一个零图，选择一个初始点加入到集合中，</br>
* 然后分别从原来顶点的集合中抽取一个顶点，</br>
* 选择的标准是构造成的树的权值最小，</br>
* 循序渐进最终生成一棵最小生成树</br>
*
* 最小生成树kruskal算法：首先将每个顶点作为一棵森林，升序比较该顶点的邻接边，</br>
* 每次取最小权值的邻接边，将该邻接边连接的顶点与原先顶点构成一棵树，接着寻找</br>
* 下一个顶点，继续按照邻接边权值升序进行比较，取权值最小的构成树...</br>
*
* 该类用一个Edge类构成一个邻接边的信息，包括邻接边的起始顶点与结束顶点，权值。</br>
* 用类Edge创建对象，录入对象信息，按照对象的权值进行比较，符合条件的对象加入</br>
* 到链表中，最终按照链表顺序输出最小生成树。</br>
* <a href="http://www.open-open.com/lib/view/open1423884996311.html">具体资料</a></br>
* <a href="http://blog.csdn.net/sinat_19650093/article/details/50978601">借鉴的资料</a>
* </p>
* <p>Company:奇点创智 </p>
* <p>Version:1.0 </p>
* @author Administrator
* @date 2017年6月6日 上午11:19:59
*/
public class MinimumTreeA {
int[][] dataMap={{-1,-1,10,-1,30,100},
{-1,-1,5,-1,-1,-1},
{-1,-1,-1,50,-1,-1},
{-1,-1,-1,-1,-1,10},
{-1,-1,-1,20,-1,60},
{-1,-1,-1,-1,-1,-1}};
/**
*
*<p>Title: findTree</p>
*<p>Description:找寻最小生成树 ，核心算法</p>
*@param start
*@param end
*@param n
*@return void
*@author Administrator
*@date 2017年6月6日 上午11:42:01
*/
public void findTree(int start,int end,int n){
int[] closedge=new int[n];//记录与当前树与可达的未被访问之前的权值
boolean[] arrivaled=new boolean[n];//记录当前点是否被访问
List<Integer> list=new ArrayList<>();//记录最小树生成树中依次添加的节点
int tempMinNode;
arrivaled[start]=true;//标记起始节点已被访问
list.add(start);//将起始节点加入最小生成树列表中
for (int i = 0; i <n; i++) {
if(!arrivaled[i]){
closedge[i]=dataMap[start][i];
}
}
for (int i = 0; i < n; i++) {
tempMinNode=findMinNode(closedge,arrivaled);
System.out.println(tempMinNode);
if(tempMinNode==-2||closedge[tempMinNode]==-1) break;
else{
arrivaled[tempMinNode]=true;
list.add(tempMinNode);
for (int j = 0; j <n; j++) {
if(!arrivaled[j]&&dataMap[tempMinNode][j]>0){
if(closedge[j]==-1||closedge[j]>dataMap[tempMinNode][j]){
closedge[j]=dataMap[tempMinNode][j];
}
}
}
}
}
System.out.println(list);
}
/**
*
*<p>Title: findMinNode</p>
*<p>Description: 找寻与当前</p>生成树链接中具有最小全值的连接节点
*@param closedge
*@param arrivaled
*@return
*@return int
*@author Administrator
*@date 2017年6月6日 上午11:40:42
*/
private int findMinNode(int[] closedge, boolean[] arrivaled) {
int size=closedge.length,min=-2;
for (int i = 0; i <size; i++) {
if(!arrivaled[i]){
if(min==-2&&closedge[i]>0)min=i;//覆盖初始节点
if(min!=-2&&closedge[min]>0){
if(closedge[i]>0&&closedge[i]<closedge[min])min=i;
}
}
}
return min;
}
/**
*
*<p>Title:print </p>
*<p>Description: 打印输出信息</p>
*@param data
*@return void
*@author Administrator
*@date 2017年6月6日 上午11:40:25
*/
public void print(int data[]){
for (int i = 0; i < data.length; i++) {
System.out.println(data[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
MinimumTreeA sh=new MinimumTreeA();
sh.findTree(1, 5, 6);
}
}