一、最小生成树

　　　　1，问题

　　　　　　最小生成树要解决的是带权图 即 网 结构的问题，就是n个顶点，用n-1条边把一个连通图连接起来，并且使得权值的和最小。可以广泛应用在修路建桥、管线运输、快递等各中网络方面。我们把构造连通图的最小代价生成树成为最小生成树。

　　　　　　最小生成树有两个算法 普里姆算法和克鲁斯卡尔算法

　　　　2，普里姆算法

　　　　　　（1）普里姆算法的思路是，从一个入口进入，找到距离入口最近的下一个结点；现在你有了两个结点，找到分别与这两个结点连通的点中，权值最小的；现在你有了三个结点，分别找到与这三个结点联通的点中，权值最小的；……

　　　　　　从思路可以看出，这就是一个切分问题。将一副加权图中的点进行区分，它的横切边中权值最小的必然属于子图的最小生成树。（横切边，指连接两个部分的顶点的边）也就是将已经找到的点，和没找到的点进行区分。

　　　　　　解决思路就是贪心算法，使用切分定理找到最小生成树的一条边，并且不断重复直到找到最小生成树的所有边。

　　　　　　（2）实现思路

　　　　　　　下面我们就来一步一步地实现普里姆算法。为了方便讨论，我们先规定一些事情。a，只考虑连通图，不考虑有不连通的子图的情况。b，只考虑每条边的权值都不同的情况，若有权值相同，会导致生成树不唯一

　　　　　　　　c，Vi的角标对应了其在vertex[]中存储的角标。 d，这里我们从V0为入口进入。e，这里我们使用的是上一篇文章实现的邻接矩阵存储的图结构。

　　　　　　首先，我们拿到一张网。

 　　　　我们从V0进入，找到与V0相连的边，邻接点和权值。我们需要容器来存储，因为是邻接矩阵存储的，所以我们这里用一维数组来存储这些元素，我们仿照书中的代码风格，定义一个adjvex[numVertex]和一个lowcost[numVertex]。这两个数组的含义和具体用法我们后面再说，现在你只需要知道它们是用来横切边，邻接点和权值的。adjvex[]的值被初始为0，因为我们从V0开始进入。lowcost[]的值被初始化为INFINITY，因为我们要通过这个数组找到最小权值，所以要初始化为一个不可能的大值，以方便后续比较，但这里的INFINITE 不需要手动设置，因为edges中已经将没有边的位置设置为了I，所以只需要在拷贝权值时同事将I也拷贝过来。

　　　　现在我们的切分只区分了V0和其他点，横切边权值有10，11，分别对应邻接点V1，V5，我们将V1，V5的对应权值按照其在vertex[]中存储的角标1，5来存入lowcost，将与V1，V5对应的邻接点V0的角标0存入adjvex[]中（其实所有顶点的邻接点对应角标都被初始化为0）。所以我们现在得到

    adjvex[]  = { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 };     lowcost[] = { 0 ,10 , I , I , I , 11 , I , I , I };

　　这里大家要理解这两个数组的含义，我再仔细解释一下。lowcost中存有非I元素的位置的下标，表示的是，横切边所连接的，没有被连入生成树的一端的顶点在vertex[]中保存的下标，在这里也等于Vi的下标，也可以理解为“刚刚被发现的结点的下标”。

　　然后adjvex[]中保存了非0元素的下标，与lowcost的中的下标是一样的意义，只不过这里因为被划分的点是0所以数组中没有非0元素。

　　lowcost中存有的非I元素，表示的是，这个位置对应的顶点与现有最小生成树的横切边中权值最小的一条边的权值。

　　adjvex中存有的非0元素，是一个顶点在vertex[]中的下标，表示的是该角标index对应的vertex[index]与adjvex[index]这两个顶点之间的权值最小，该权值是lowcost[index]。

　　这样大家应该能够对大话数据结构中这一部分有完整的理解了。　　　

　　我们现在从lowcost[]中找到最小的权值，然后将该权值对应的顶点加入最小生成树。加入的方式是将该权值置为0，并且将该新结点的邻接点在adjvex中对应的角标置为该新结点的index。

　　对应现在的情况，就是把V1加入生成树，把两个数组调整如下：

    adjvex[]  = { 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1 };     lowcost[] = { I , 0 , 18, I , I ,11 , 16, I , 12};

接下来我们有四条待选边，lowcost中找到最小的非零权值是11，对应index为5，去vertex[5]找到V5，所以此时V5加入生成树，将lowcost[5]置为0，V5的邻接点加入adjvex和lowcost，如下

    adjvex[]  = { 0 , 0 , 1 , 0 , 5 , 0 , 1 , 0 , 1 };     lowcost[] = { I , 0 , 18, I , 26, 0 , 16, I , 12};

 反复重复上面的动作v-1次，此时就加入了v-1条边，得到了最小生成树。

代码实现如下：

    public void MiniSpanTree_Prim(){          int[] adjvex = new int[numVertex];         int[] lowcost = new int[numVertex];          adjvex[0] = 0;         lowcost[0] = 0;         /*         for (int i = 1; i < numVertex; i++){             lowcost[i] = INFINITY;         }           */        for (int i = 1; i < numVertex; i++)         {             lowcost[i] = edges[0][i];             adjvex[0] = 0;         }          for (int i = 1; i < numVertex; i++){             int min = INFINITY;             int k = 0;             for (int j = 1; j < numVertex; j++){                 if (lowcost[j] != 0 && lowcost[j] < mi