生成树

生成树是连通图的一个极小连通子图，它是含有图的全部节点，但只有构成树的(n-1)条边

最小生成树

最小生成树是在生成树的基础上，要求树的(n-1)条边的权值之和最小

  1. 必须使用该图中的n-1条边连接图中的n个顶点
  2. 不能产生回路
  3. 要使树的n-1条边的权值之和是最小的

Prim算法

思想

通过选点来构造最小生成树，每次选择“未加入”且“加入后使得构造的当前生成树最小”的点来构造最小生成树

步骤

  1. 初始化u={v}
  2. 重复以下步骤，直到所有的点加入u中
    1. 从侯选边中挑选距离最小的边，并将对应的顶点加入
    2. 根据当前的结果，更新侯选边及距离

代码

#include<iostream>

using namespace std;

int main(){
    //n为顶点数，m为要输入边数 ,sum为树的权值 
    int n=0,m=0,sum=0,max=0x7fffffff;
    //用邻接矩阵来存边的权值 
    int edge[101][101]={},set[101]={0},dist[101]={0x7fffffff};
    //读取数据 
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
                edge[i][j]=max;
        }
    int tempi=0,tempj=0;
    for(int i=1;i<=m;i++){
            cin>>tempi>>tempj;
            cin>>edge[tempi][tempj];
            edge[tempj][tempi]=edge[tempi][tempj];
            } 
    //初始化prim算法
    set[1]=1;
    for(int i=1;i<=n;i++){
            dist[i]=edge[1][i];
            }
    //prim
    for(int i=2;i<=n;i++){
            //选最近的点 
            int tempv=0,tempdist=max;
            for(int j=1;j<=n;j++){
                    if(set[j]==0&&dist[j]<tempdist){
                          tempv=j;
                          tempdist=dist[j];
                          }
                    }
            //将点加入树种 
            set[tempv]=1;
            sum+=dist[tempv]; 
            //刷新距离
            for(int j=1;j<=n;j++){
                    if(set[j]==0&&edge[tempv][j]<dist[j])
                         dist[j]=edge[tempv][j];
                    } 
            cout<<"本次选取了"<<tempv<<"号节点"<<dist[tempv]<<endl; 
            }
    cout<<"最小权值为"<<sum;
    cin>>n; 
    return 0;   
    }