数据结构（构造连通网的最小生成树）

普利姆算法

形象问题：几个村庄之间有N条路，要再路边修下水管道，求在那些路上修管道能在全部村庄连通的基础上使修的管道最短

中心思想：从一个顶点逐渐连接到全部顶点；在连接过程中找权最小的边加入生成树中

方法

• 规定从第一个结点出发，找到连接的边中权最小的
• 将这条边加入生成树中
• 循环①，②步，不断找到连接一个顶点的权最小的边，直到连接玩全部顶点
• 顶点和这些边就构成了连通网的最小生成树

//G是一个图结构体：
//numVertexes：顶点个数
//arc:邻接矩阵
void MinSpanTree_prim(MGraph G){
    int min , i , j , k;
    int adjvax[MAXVEX];//到该位置对应顶点的最短路径的边的另一个顶点【方便找到边后打印这条边的两个顶点下标】
    int lowcost[MAXVEX];//连接到下标对应顶点的边的最小权【为0表示已经找到；INFINITY表示还没找到；其他表示：目前为止的值】
            //既然说是目前为止，是因为以后连接到其他顶点，还会添加可选择的边；在这些新加的边中可能会刷新连接它的边的权最小记录

    lowcost[0]=0;//第一个顶点作为最小生成树的根，权直接为0
    adjvax[0]=0;//第一个顶点先加入

    //初始化操作
    for(i=1;i<G.numVertexes;i++){
        lowcost[i]=G.arc[0][i];//将邻接矩阵第0行所有权值加入数组（从第一个顶点开始到其他顶点的权）
        adjvax[i]=0;//初始化全部为第一个顶点的下标
    }

    //开始构建最下生成树
    for(i=1;i<G.numVertexes;i++){//连接N个顶点，找N-1条边，分别从一个顶点找到其他N-1个顶点
        min = INFINITY;//记录最小权值；初始化为65535；
        j=1;//循环使用的索引值
        k=0;//记录这次连接到的顶点的下标

        //遍历全部顶点
        while(j<G.numVertexes){//找到可连接的最小权
            if(lowcost[j]!=0 && lowcost[j]<min){
                min=lowcost[j];
                k=j;//将找到的最小权值下标存入k;
            }
            j++;
        }

        printf("(%d,%d)  ",adjcex[k],k);//打印当前顶点边中权值最小的边；adjcex[k]，边的起始下标；k,当前位置
        lowcost[k]=0;//将当前顶点的权值设置为0，表示此顶点已经连接到生成树中，继续进行连接下一个顶点

        //邻接矩阵k行逐个遍历全部顶点
        for(j=1;j<G.numVertexes;j++){
            if(lowcost[j]!=0 && G.[k][j] < lowcost[j]){
                lowcost[j]=G.arc[k][j];//刚刚连接的顶点下标k，连接到j位置顶点的权小于原先连接到j位置的权；那么就刷新连接他的最小权
                adjvax[j]=k;//将刷新连接j位置最小权的顶点的下标记录到adjvax数组j位置下；利用该值打印这条权最小记录的边:（adjvax[k],k）
            }
        }
    }
}

克鲁斯卡尔算法

直接去找权最小的边来构建生成树（构建过程中只要避免构成环即可）

方法

• 将图中所有边以权排序成边集，图中顶点去掉全部边（构成树林）
• 遍历边集数组，检测每条边依附的两顶点是否在同一颗树中【不在的话连接两顶点(树)组成一颗树；若在连接后就会构成环，所以舍弃这种边】
• 遍历完边集数组时就构造出了最小生成树

int find(int *parent,int f){
    while(parent[f]>0){
        f=parent[f];
    }
    return f;
}
//parent数组：存储当前位置对应顶点在一棵树上的另一个顶点的对应下标
    //所以刚开始时，存储下标对应的顶点是与自身位置对应顶点是直接相连的
    //当这个位置构建最小生成树会直接相连一个顶点以上时，那么下一个连接顶点下标会存储在第一个连接下标顶点对应位置
    //例如:0下标顶点构建最小生成树时会连接1下标和3下标两个顶点对应位置顶点；那么：parent[0]=1;parent[1]=3;或者parent[0]=3;parent[3]=1
//总之parent数组中将同一颗树顶点的下标利用类似链表的方法连接在一起；
    //给f传入一颗树任意顶点对应的下标返回的值（x）都是一样的；并且在parent[x]这个位置是存放这颗树下一次新加的顶点下标的

//Kruskal算法生成最小生成树
void MiniSpanTree_Kruskal(MGraph G){
    int i,n,m;
    Edge edges[MAGEDGE];//定义边集数组
    int parent[MAGEDGE];//定义parent数组用来判断边与边是否形成环路

    for(i=0;i<G.numVertexes;i++){
        parent[i]=0;
    }
    for(i=0;i<G.numEdges;i++){
        //edges:边集数组；边的结构：begin，起点；end,终点；weight，这条边的权
        //n得到的是edges[i].begin这个下标所属树下一次新加顶点下标在prent数组中存储位置
        //m得到的值也有edges[i].end顶点所属树的相同作用
        //所以m==n就说明两顶点属于同一颗树（已经间接连接了，不需要再重复直接连接了；也就是不要形成环路）
        //只有所属不同树时才同时有添加的能力，合并两棵树相当于要用掉一棵树的添加能力，合并后的数的添加能力就要原先被添加树承担
        n=find(parent,edges[i].begin);
        m=find(parent,edges[i].end);
        if(n!=m){//如果n==m,则形成环路
            parent[n]=m;//将此边的结尾顶点放入下标起点的parent数组中，表示此顶点已经在生成树集合中
            printf("(%d,%d)%d  ",edges[i].begin,edges[i].end,edges[i].weight);
        }
    }
}