概念

最小生成树

连通图的生成树是一个极小的连通子图，含有图中全部的n个顶点，但最多只有n-1条边。通常把构成连通图的最小代价的连通路径，称为最小生成树。

最小生成树的两个算法

Prim算法（普利姆）

图1.算法中的邻接矩阵

思路

1.定义两个数组：adjvex保存相关顶点下标，默认值为0；lowcost保存顶点之间的权值，默认值∞，其数组大小都为顶点数目
2.从邻接矩阵V0开始寻找连接顶点，默认它为最小生成树的第一个顶点；
3.遍历lowcost，根据权值最小，找到连接点k，然后更新k的权值为0，标识已访问过
4.遍历所有顶点，找到跟k相连且未访问过的顶点，记入adjvex，同时比较权值，较小值存入lowcost

//邻接矩阵结构
typedef struct {
    int arc[MAXVUE][MAXVUE];
    int numVertexes, numEdges;//顶点数和边数
} MGraph;

void MiniSpanTree_Prim(MGraph G) {
    int adjvex[MAXVUE];
    int lowcost[MAXVUE];
    
    lowcost[0] = 0;
    adjvex[0] = 0;
    
    int i, min, j, k;
    int sum = 0;
    
    for (i=1; i<G.numVertexes; i++) {
        lowcost[i] = G.arc[0][i];
        adjvex[i] = 0;
    }
    
    for (i=1; i<G.numVertexes; i++) {
        min = INFINITYC;
        j=1;
        k=0;
        
        //找到最小权值和下标
        while (j<G.numVertexes) {
            if (lowcost[j]!=0 && lowcost[j]<min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        
        printf("(V%d,V%d)=%d\n",adjvex[k],k,G.arc[adjvex[k]][k]);
        sum += G.arc[adjvex[k]][k];
        
        //已访问
        lowcost[k] = 0;
        
        //更新lowcost、adjvex
        //找到与k点相连的顶点
        for(j=1; j<G.numVertexes; j++) {
            if (lowcost[j]!=0 && G.arc[k][j] < lowcost[j]) {
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;
            }
        }
    }
    printf("sum=%d\n",sum);
}

Kruskal算法（克鲁斯卡尔）

思路

图2.Kruskal的边表数组

1.将邻接矩阵 转换为 边表数组

//边表数组的结构
typedef struct {
    int begin;
    int end;
    int weight;
}Edge;

2.对数组根据权值进行从小到大排序
3.初始化parent，默认为0，这里保存顶点之间的连接关系
4.遍历所有的边（begin-end），在parent中寻找begin和end的连接关系，并保存，同时保证它们不会形成闭环。通过parent寻找终点，终点一致则是闭环
5.（begin-end）没有闭环，则加入到最小生成树种，并更新parent数组

//值交换
void Swapn(Edge *edges,int i, int j) {
    int tempValue;
    
    tempValue = edges[i].begin;
    edges[i].begin = edges[j].begin;
    edges[j].begin = tempValue;
    
    tempValue = edges[i].end;
    edges[i].end = edges[j].end;
    edges[j].end = tempValue;
    
    tempValue = edges[i].weight;
    edges[i].weight = edges[j].weight;
    edges[j].weight = tempValue;
}
//排序
void Sort(Edge edges[],int numEdges) {
    int i, j;
    for (i=0; i<numEdges; i++) {
        for (j=i+1; j<numEdges; j++) {
            if (edges[i].weight>edges[j].weight) {
                Swapn(edges,i,j);
            }
        }
    }
    
    printf("边集数组根据权值排序之后的为:\n");
    for (i = 0; i < numEdges; i++)
    {
        printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
    }
}
//寻找顶点的终点，并返回
int Find(int *parent,int f) {
    while (parent[f]>0) {
        f = parent[f];
    }
    return f;
}

void MiniSpanTree_Kruskal(MGraph G) {
    int i,j,n,m;
    int sum = 0;
    int k = 0;
    
    int parent[MAXVUE] = {0};
    Edge edges[MAXVUE];
    
    //构建边表数组
    for(i=0; i<G.numVertexes; i++) {
        for (j=i+1; j<G.numVertexes; j++) {
            if (G.arc[i][j]<INFINITYC) {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.arc[i][j];
                
                k++;
            }
        }
    }
    
    //对边表数组排序
    Sort(edges, G.numEdges);
    
    printf("打印最小生成树：\n");
    
    //循环所有边
    for (i=0; i<G.numEdges; i++) {
        
        //获取begin,end 在parent 数组中的信息;
        //如果n = m ,将begin 和 end 连接,就会产生闭合的环.
        n = Find(parent,edges[i].begin);
        m = Find(parent,edges[i].end);
        
        if (n!=m) {
            /* 将此边的结尾顶点放入下标为起点的parent中。 */
            /* 表示此顶点已经在生成树集合中 */
            parent[n] = m;
            
            /*打印最小生成树路径*/
            printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
            sum += edges[i].weight;
        }
    }
    printf("sum = %d\n",sum);
}