最小生成树

    对于一个连通网（连通带权图，假定每条 边上的权均为大于零的实数）来说，每棵 树的权（即树中所有边的权值总和）也可能不同 具有权最小的生成树称为最小生成树。

       最小生成树问题主要有三个算法；分别是：prim算法，Kruskal算法以及将prim与堆结合的prim+heap算法。

  参考资料 ：    三种算法的效率比较，以及各个情况下的选择

   本文是三种算法中最复杂的prim+heap算法，本文尝试对每句代码进行注解，将我的理解尽可能详细地表达出来。

#include<iostream>

#include<cstdio>//本头文件在程序中可以不加，本次加上是由于个人习惯

                            //（也就是说我还处于半c++半c状态）

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

const int INF=1<<30;//定义一个“无穷大的”变量，相当于对1进行30次左移运算 ，2^30.

 //相关资料：位运算

struct Edge{//定义结构体，对一个节点的临接点及路径权值进行记录

int v;

int w;

Edge(int v_,int w_):v(v_),w(w_){}//相当于定义一个函数（或说是一种方法）对v,w赋初值

bool operator<(const Edge&a)const{//这里有一些试错

return w>a.w;//在后面的队列里，边权值越小越优先 

                    //（至于为什么要用，读到后面就可以明白了）

}

};//这一块有问题不是很清楚，打算以后再填这个坑

vector<vector<Edge> >G(100);//利用vector建立二维数组 ，此处有一个注意点就是：

                                          // “vector<vector<Edge>(此处必须有空格)>G（100）”，

                                          //因为"> >"和输入要用的">>"过于相似

int HeapPrim(const vector<vector<Edge> >G,int n){//G为图，n为途中所有结点的数量

int Toln=0;//定义最小生成树中的结点值 

                //与n不同的是“Toln”标识的是当前“最小生成树”中的节点数量

int Tolw=0;//定义最小生成树的（当前）最小权值

vector<int>vUsed(n);//定义数组，标识该点是否在最小生成树中

vector<int>vDist(n);//定义数组，标识每个最小生成树外节点与最小生成树的距离

Edge xDist(0,0);//定义变量；

priority_queue<Edge>pq;//定义优先队列

pq.push(Edge(0,0));//将一个节点压入优先队列 

for(int i=0;i<n;i++){

vUsed[i]=0;//所有结点没有被访问

vDist[i]=INF;//赋值前所有结点间的距离都为无穷大

}

while(Toln<n&&!pq.empty()){

do{//"do{}while;"语句，如果节点被访问，且队列非空的情况下

xDist=pq.top();//将队列中的第一个赋值给xDist变量，这也就是为什么在上面定义结构体时 

                        //要重载“bool operator<”,在本优先队列中，边权值小的永远在前面

                        //这里xDist取第一个值，那就是取队列中边权值最小的

pq.pop();//删除第一个值；

}while(vUsed[xDist.v]==1&&!pq.empty());

if(vUsed[xDist.v]==0){//节点没有被访问

Toln++;//Toln加一

vUsed[xDist.v]=1;//标记已在最小生成树中

Tolw+=xDist.w;//最小生成树权值增加

for(int i=0;i<G[xDist.v].size();i++){//对xDist.v的邻接点的数据进行更新

int k=G[xDist.v][i].v;//k为与xDist.v相接的点 ，从第一个相接的点遍历至最后一个

if(vUsed[k]==0){//如果k没有被访问过，就进行操作

int w=G[xDist.v][i].w;//w为xDist.v 和节点k的距离

if(w<vDist[k]){//如果w小于节点k距离最小生成树的距离，就对vDist[k]进行更新

vDist[k]=w;

pq.push(Edge(k,w));//只有 w小于节点k距离最小生成树的距离的时候，再将k点压入队列

                    }

                }

            }

        }

}

if(Toln<n)

return -1;

else

return Tolw;

}

int main(){

int n;

while(cin>>n){

 for(int i=0;i<n;i++)

 G[i].clear();

//G.clear(); //此处使用有误，可能会由于前面的各种东西太多。

                //导致此步错误，如果使用的是此语句。

                //那么程序可以通过调试，但无法给出答案

for(int i=0;i<n;i++)

for(int j=0;j<n;j++){

int w;

cin>>w;

G[i].push_back(Edge(j,w));

}

cout<<HeapPrim(G,n)<<endl;

}

return 0;

}