使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义， n 个顶点的连通网络的生成树有 n 个顶点、 n - 1 条边。 构造最小生成树    假设有一个网络，用以表示 n 个城市之间架设通信线路，边上的权值代表架设通信线路的成本。如何架设才能使线路架设的成本达到最小？

 

经过算法优化后得到这个树 

 

 所以，这种问题的解决方法通俗的有两种：

普里姆（prim）算法

克鲁斯卡尔（Kruskal）算法

我们首先来入手Kruskal算法

Kruskal

Kruskal算法的基本思想：从边入手找顶点（贪心法）

步骤：

1.先构造一个只含 n 个顶点的子图 SG;

2.然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边

3.反复执行第2步，直至加上 n-1 条边为止。

（下图中浅色的就是舍弃掉的边，根据上面的描述很快能理解这个图） 

 

 下面的算法描述中，适用并查集来做 

/*
构造非连通图 ST=( V,{ } );
k = i = 0; // k 计选中的边数
while (k<n-1)
{
    ++i;
    检查边集 E 中第 i 条权值最小的边(u,v);
    若(u,v)加入ST后不使ST中产生回路，则 输出边(u,v); 且 k++;
}
*/

 还没学到并查集。。等学到了再补充（听说要用到路径压缩？！）

先放大佬博客最小生成树（kruskal算法）_Superb_day-CSDN博客

 

Prim

普里姆算法的基本思想: 从顶点入手找边 [贪心法 ]

实施步骤：

1.分组，出发点为第一组，其余结点为第二组。

2.在一端属于第一组和另一端属于第二组的边中选择一条权值最小的一条。

3.把原属于第二组的结点放入第一组中。

4.反复2，3两步，直到第二组为空为止

 图示手工

这两张图联合在一起看，很好理解的 

 

 

 实现代码

#include<iostream.h>
#define M 20
int G[M][M];int n;
void Prim()
{ 
    int temp[M]; //存放已经加入的结点
    int size; // 已加入的结点个数
    int i,j,k; 
    int curnode,pos1,pos2;
    int min;
    temp[0]=0; size=1;
    G[0][0]=1;
    for( i=0;i<n-1;i++)
    {
        min=32767; // 极大值
        for ( j=0;j<size;j++)
        {
            curnode=temp[j];
                for( k=0;k<n;k++)
                    if ( G[curnode][k]<min && G[k][k]==0){ 
                    min=G[curnode][k]; pos1=curnode;
                    pos2=k; 
                    }
        }
     cout<<"edge "<<size<<" ( "<<pos1<<" -----> "<<pos2<<" ):" <<G[pos1][pos2]<<endl;
     G[pos2][pos2]=1;
     temp[size]=pos2; 
     size++;
    }
}

void Input()
{
    cin>>n;
    for(i=0;i<n;i++)
        for (j=0;j<n;j++)
            cin>>G[i][j];
}

void main()
{ 
    cout<<"please input the data of graph:"<<endl;
    Input(); 
    Prim();
}