最小生成树

一个有n个节点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。最小生成树可以用Kruskal算法或者prim算法求出。

kruskal 算法的过程为不断对子图进行合并，直到形成最终的最小生成树。prim 算法的过程则是只存在一个子图，不断选择顶点加入到该子图中，即通过对子图进行扩张，直到形成最终的最小生成树。

https://www.jianshu.com/p/cf21443b3838

此网址对着两种算法做了详细介绍

prim算法

最小生成树的一个典型问题

poj-1258

题意：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

输入：输入包含多组数据。对于每组数据, 第一行包含一个整数N表示农场的数量 (3 <= N <= 100). 接下来是一个N*N的邻接矩阵,表示各个村庄之间的距离 . 当然，对角线将是0，因为从农场到农场的距离对于这个问题并不有趣。

输出：对于每种情况，请输出一个整数表示长度，该长度是连接整个农场集合所需的最小光纤长度的总和。

#include<iostream>
#include<cstring>
using namespace std;
int init[105][105],N;//无向图的邻接矩阵
int vis[105]={0},mincost[105];//vis标记已经走过的节点,mincoat表示从x定点出发的边到每个顶点的最小权值
/************************最小生成树的prim算法************************/
int prim()//从某个顶点出发，不断添加边
{
    int minsum=0;//最小边之和
    vis[0]=1;//从第一个顶点开始，标记
    for(int i=0;i<N;i++)
        mincost[i]=init[0][i];//标记从第一个顶点出发的边的最小权值
    for(int i=1;i<N;i++){
        int MIN=100005,node;//MIN的一般写法是MIN=inf
        for(int j=1;j<N;j++){
            if(!vis[j]&&mincost[j]<MIN){//比较权值，寻找下一个顶点
                MIN=mincost[j];
                node=j;//标记权值最小的顶点
            }
        }
        //用来处理无法连通的问题
        //if(MIN==inf){
        //    cout<<"NO"<<endl;
        //    return;
        //}
        vis[node]=1;//标记权值最小的顶点
        minsum+=MIN;//题目答案，最小和相加
        for(int j=1;j<N;j++){
            if(!vis[j]&&mincost[j]>init[node][j])
                mincost[j]=init[node][j];//找出当前顶点下与上一顶点下的最小权值
        }
    }
    return minsum;//求得题目最终的最小和
}
int main()
{
    while(cin>>N)
    {
        memset(init,0,sizeof(init));
        memset(vis,0,sizeof(vis));
        memset(mincost,0,sizeof(mincost));
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
            cin>>init[i][j];
        cout<<prim()<<endl;
    }
    return 0;
}