最小生成树-普利姆算法

详细的说明代码中已经差不多了,不再赘述：

用到的图如下:

#include <stdio.h>
#include <stdlib.h>
typedef struct e{
    int otherVertex;//保存另一条边的标号
    int edgeWeight;//保存另一条边的权重
} Edge;
void prim(int *edge,int vertexNum);
int main(){
    puts("***************普利姆算法(求连通图分最小生成树)****************");
    puts("***************************************************************");
    puts("最小生成树:包括n各顶点，但是只有n-1个边的一棵树,想要使权值相加为最小.");
    //这里把图写死了，只是为了实现这个算法
    int edge[6][6]={0};
    int i ,j;
    edge[0][1] = 6;
    edge[0][2] = 1;
    edge[0][3] = 5;
    edge[1][2] = 5;
    edge[2][3] = 5;
    edge[2][5] = 4;
    edge[1][4] = 3;
    edge[2][4] = 6;
    edge[3][5] = 2;
    edge[4][5] = 6;

    edge[1][0] = 6;
    edge[2][0] = 1;
    edge[3][0] = 5;
    edge[2][1] = 5;
    edge[3][2] = 5;
    edge[5][2] = 4;
    edge[4][1] = 3;
    edge[4][2] = 6;
    edge[5][3] = 2;
    edge[5][4] = 6;
    prim(edge,6);
    return 0;
}

void prim(int *edge,int vertexNum){
    Edge *closeEdge;
    int i;
    closeEdge = (Edge *)malloc(sizeof(Edge)*vertexNum); //候选集合中的点到生成树中的点的一组最小边
    //顶点集合的下标代表一个顶点的标号 如果而值1代表改点存在该集合中0代表该点不存在该集合
    int *U = (int *)malloc(sizeof(int)*vertexNum);//生成树顶点集合
    int *S_U = (int *)malloc(sizeof(int)*vertexNum);//候选集合顶点 它和U集合的顶点是互补的
    //初始化U集合和S_U集合
    U[0]= 1;//将0标号这个点放入集合中
    S_U[0] = 0;//将0标号的点移除S_U集合
    for(i = 1;i<vertexNum;i++){
        U[i]=0;
        S_U[i]=1;
    }
    //初始化closeEdge 如果一个顶点已经在生成树集合中 就不需要在closeEdge中出现了
    closeEdge[0].otherVertex = 0;
    closeEdge[0].edgeWeight = 0;
    for(i=1;i<vertexNum;i++){
        int weight = *(edge+vertexNum*0+i);
        if(weight!=0){
            closeEdge[i].otherVertex = 0;
            closeEdge[i].edgeWeight = weight;
        }
    }
    int j =0;
    //开始普里姆算法 找出n-1条边，一次循环一条边
    for(i = 1;i<vertexNum;i++){
        //从closeEdge中找出权值最小的边
        int minVertexIndex = minWeight(closeEdge,vertexNum,S_U);
        //将该顶点加入U中，并从S_U中移除
        U[minVertexIndex] = 1;
        S_U[minVertexIndex] =0;
        printf("(%d,%d);",closeEdge[minVertexIndex].otherVertex+1,minVertexIndex+1);
        //更新closeEdge  也就是新加入到S集合(生成树集合)中的顶点到S_U集合(候选集合)中的顶点是否存在权值更小的边，如果有，那么更新它
        for(j=0;j<vertexNum;j++){
            //如果该点在候选集合中存在 并且该点是顶点S集合中顶点minVertexIndex的邻接边
            if(S_U[j]&&*(edge+vertexNum*minVertexIndex+j)!=0){
                if(*(edge+vertexNum*minVertexIndex+j)<closeEdge[j].edgeWeight){
                    closeEdge[j].otherVertex = minVertexIndex;
                    closeEdge[j].edgeWeight = *(edge+vertexNum*minVertexIndex+j);
                }
            }
        }
    }
    i = 0;

    puts("\n输出closeEdge:");
    for(i;i<vertexNum;i++){
        printf("(%d,%d),权重:%d;",closeEdge[i].otherVertex+1,i+1,closeEdge[i].edgeWeight);
    }
}

//返回最小权值边的顶点中在S_U中的顶点的下标
int minWeight(Edge *closeEdge,int vertexNum,int *S_U){
   int i = 1,minVertexIndex = vertexNum,minWeight = 9999999; //权值只能小于9999999 不然会出错
   for(i = 0;i<vertexNum;i++){
        if(S_U[i]&&closeEdge[i].edgeWeight <minWeight){//如果该点存在在S_U中 并且权重小于minWeight
                minWeight = closeEdge[i].edgeWeight;
                minVertexIndex = i;
        }
   }
   return minVertexIndex;
}

输出结果如下:

***************普利姆算法(求连通图分最小生成树)****************
***************************************************************
最小生成树:包括n各顶点，但是只有n-1个边的一棵树,想要使权值相加为最小.
(1,3);(3,6);(6,4);(3,2);(2,5);
输出closeEdge:
(1,1),权重:0;(3,2),权重:5;(1,3),权重:1;(6,4),权重:2;(2,5),权重:3;(3,6),权重:4;