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); }}
转载于:https://www.cnblogs.com/1x-zfd50/p/6959036.html
