Go语言视频零基础入门到精通

javalearner

1、生成树
如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。
生成树是连通图的包含图中的所有顶点的极小连通子图。
图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。


2、 最小生成树
   对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权， 权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。 3、生成树和最小生成树的应用
生成树和最小生成树有许多重要的应用。
【例】网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。 4、最小生成树性质（MST性质）
MST性质
最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u，v)。

注：将集合U中的顶点看作是红色顶点，②而V-U中的顶点看作是蓝色顶点，③连接红点和蓝点的边看作是紫色边，④权最小的紫边称为轻边(即权重最"轻"的边)。于是，MST性质中所述的边(u，v)就可简称为轻边。
  4、求MST的一般算法描述
求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边(u，v)，最终生成一棵含n-1条边的MST。
当一条边(u，v)加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。

用伪代码可将算法描述为：
GenerieMST(G){//求G的某棵MST
   T={}； //T初始为空，是指顶点集和边集均空
   while T未形成G的生成树 do{
      找出T的一条安全边(u，v)；//即T∪{(u，v)}仍为MST的子集
      T=T∪{(u，v)}； //加入安全边，扩充T
    }
   return T； //T为生成树且是G的一棵MST
}

5、普里姆(Prim)算法


（1）算法思想
T=(U，TE)是存放MST的集合。
①T的初值是({r}，￠)
即最小生成树初始时只有一个红点r，没有红边。
②T经过n-1次如下步骤操作，最后得到一棵含n个顶点，n-1条边的最小生成树
        ⒈选择紫边集中一条轻边并扩充进T
⒉将轻边连接的蓝点改红点
⒊将轻边改红边
        ⒋修改紫边集 （2）较小紫边集的构造
     若当前形成的T中有k个顶点，|U|=k，|V-u|=n-k，故可能的紫边数目是k(n-k)。从如此大的紫边集中选择轻边是低效的。因此，必须构造较小的紫边集。

    对于每个蓝点v ∈V-U，从v到各红点的紫边中，只有最短的那一条才有可能是轻边。因此，只须保留所有n-k个蓝点所关联的最短紫边作为轻边的候选集即可。 （3）候选紫边集合的修改
     当把轻边(u，v)扩充到T时，因为v由蓝变红，故对每个剩余的蓝点j，边(v，j)就由非紫边变为紫边，这条新紫边的长度可能小于蓝点j原来所关联的最短紫边的长度。因此，用长度更小的新紫边取代那些原有的最短紫边。 （4）Prim算法的伪代码描述
PrimMST(G，T，r){
   //求图G的以r为根的MST，结果放在T=(U，TE)中
   InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)
   for(k=0；k<n-1；k++){ //求T的n-1条树边
     (u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；
    T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U
    ModifyCandidateSet(…)； //根据新红点v调整候选轻边集
   }
} （5） 算法的执行过程
用PRIM算法得到最小生成树的过程【参见动画演示】   
   

注意：
若候选轻边集中的轻边不止一条，可任选其中的一条扩充到T中。
连通网的最小生成树不一定是惟一的，但它们的权相等。
  （6）算法特点
该算法的特点是当前形成的集合T始终是一棵树。将T中U和TE分别看作红点和红边集，V-U看作蓝点集。算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。MST性质保证了此边是安全的。T从任意的根r开始，并逐渐生长直至U=V，即T包含了 C中所有的顶点为止。MST性质确保此时的T是G的一棵MST。因为每次添加的边是使树中的权尽可能小，因此这是一种"贪心"的策略。
（7）算法分析
该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。 代码：

1. import java.io.BufferedInputStream;
   
2. import java.util.Scanner;
   
3. import java.util.Arrays;
   
4. public class PrimTest{
   
5.     private int[][] arr;//邻接矩阵
   
6.     private boolean flag[];  //用来标记节点是否已加入到MST,flag[i]=true表示i点变红，加入到MST
   
7.     private int n; //顶点数
   
8.     private int sum;//最小权值和
   
9.     static final int maxInt = Integer.MAX_VALUE;
   
10.     public PrimTest(int[][] arr,int n){
    
11.          this.arr=arr;
    
12.          this.n=n;
    
13.          flag=new boolean[n];
    
14.     }
    
15.             
    
16.      
    
17.       public int prim(){
    
18.             sum = 0;
    
19.             flag[0] = true; //选取第一个节点为红点,将"0"加入红点集，开始时，所有点都是蓝点
    
20.             int mst[]=new int[n];//用来存储最小权值边的起点
    
21.             Arrays.fill(mst,0);//起点默认为0
    
22. 
    
23.             
    
24.             for(int k=1; k< n; k++){    //循环n-1次，选取n-1条边
    
25.                 int min = maxInt,min_i = 0;
    
26.                 for(int i=0; i< n; i++){//在所有紫边中选一条权值最小的。蓝点与红点连接的边为紫边
    
27.                     if( !flag[i] && arr[0][i] < min){
    
28.                         min = arr[0][i];
    
29.                         min_i = i;
    
30.                     }
    
31.                 }
    
32.                
    
33.                 flag[min_i] = true; //找到红点min_i,标记它
    
34.                 System.out.print("边"+mst[min_i]+"-"+min_i);
    
35.                  System.out.println("--"+arr[0][min_i]);
    
36.                  //arr[0][i]用来存放以i为终点的紫边的最小权值
    
37.                 for(int i=0; i< n; i++){ //因为新增了一个红点，紫边集有了变化，
    
38.                     if( !flag[i] && arr[0][i] > arr[min_i][i]){//若同一个蓝点点与两个红点相连接，取权值较小的。
    
39.                         arr[0][i] = arr[min_i][i];
    
40.                         mst[i] = min_i;//更新较小权值边的起点
    
41.                    }
    
42.                   
    
43.                 }
    
44.               
    
45.                 sum += arr[0][min_i];//加上权值
    
46.             }
    
47.             
    
48.             
    
49.            return sum;
    
50.             
    
51.         }
    
52.    
    
53.     public static void main(String[] args) {
    
54.         Scanner s = new Scanner(new BufferedInputStream(System.in));
    
55.             
    
56.             int n = 7;
    
57.             int arr[][] ={{maxInt,28,    maxInt,maxInt,maxInt, 10,    maxInt},
    
58.                  {28,    maxInt,16,    maxInt,maxInt, maxInt,14     },
    
59.                  {maxInt,16,    maxInt,12,    maxInt, maxInt,maxInt},
    
60.                  {maxInt,maxInt,12,    maxInt,22,     maxInt,18    },
    
61.                  {maxInt,maxInt,maxInt,22,    maxInt, 25,    24    },
    
62.                  {10,    maxInt,maxInt,maxInt,25,     maxInt,maxInt},
    
63.                  {maxInt,14,    maxInt,18,    24,     maxInt,maxInt}};
    
64.           System.out.println(new PrimTest(arr,n).prim());
    
65.             
    
66.      }
    
67. }

复制代码

运行结果：
C:        est>java PrimTest
边0-5--10
边5-4--25
边4-3--22
边3-2--12
边2-1--16
边1-6--14
99

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/12/7/000709078.zip