Kruskal 算法

复杂度：E log(2E)

int F[MAXN];//并查集使用struct Edge{    int u,v,w;}edge[MAXM];//存储边的信息，包括起点/终点/权值int tol;//边数，加边前赋值为0void addedge(int u,int v,int w){    edge[tol].u=u;    edge[tol].v=v;    edge[tol++].w=w;}bool cmp(Edge a,Edge b){
    //排序函数，讲边按照权值从小到大排序    return a.w

 

 

Prime算法

复杂度：N^2

const int INF=0x3f3f3f3f;const int MAXN=110;bool vis[MAXN];int lowc[MAXN];//返回最小生成树权值，不连通时返回-1；//cost[][]:耗费矩阵int Prim(int cost[][MAXN],int n)//点是0~n-1{    int ans=0;    memset(vis,false,sizeof(vis));    vis[0]=true;    for(int i=1;i
     
      lowc[j])        {            minc=lowc[j];            p=j;        }        if(minc==INF) return -1;//原图不连通        ans+=minc;        vis[p]=true;        for(int j=0;j
      
       cost[p][j])        lowc[j]=cost[p][j];    }    return ans;}