一、定义
- 连通图的生成树是一个极小的连通子图。
- 连通图的生成树含有图中全部的顶点。
- 只有足以构成一棵树的n-1条边。
最小生成树：我们把构造连通网的最小代价生成树称为最小生成树。
找连通网的最小生成树经典算法有两种：普里姆算法和克鲁斯卡尔算法。
二、普里姆算法（Prim算法）
算法思路
- 定义两个数组：adjvex和lowcost；其中adjvex用来保存相关顶点的下标；lowcost用来保存顶点之间的权值。
- 初始化两个数组，从V0开始寻找最小生成树，默认V0是最小生成树上的第一个顶点。
- 循环lowcost数组，根据权值（权值最小）找到顶点k。此时表示，V0-Vk最小生成树的第一条边。
- 更新lowcost[k]=0表示已经将顶点k加入到生成树中。
- 循环所有顶点，找到与顶点k有关系的顶点，并将与k顶点之间的权值与lowcost数组中的权值进行比较，并较小的权值更新lowcost数组。
- 更新权值的时候，同步需要更新adjvex中的顶点下标。因为此时遍历的是与k顶点有关系的顶点，所以需要将adjvex对应的下标设置为k。
算法的代码实现
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/*9.1 创建邻接矩阵*/
void CreateMGraph(MGraph *G)/* 构件图 */
{
int i, j;
/* printf("请输入边数和顶点数:"); */
G->numEdges=15;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITYC;
}
}
G->arc[0][1]=10;
G->arc[0][5]=11;
G->arc[1][2]=18;
G->arc[1][8]=12;
G->arc[1][6]=16;
G->arc[2][8]=8;
G->arc[2][3]=22;
G->arc[3][8]=21;
G->arc[3][6]=24;
G->arc[3][7]=16;
G->arc[3][4]=20;
G->arc[4][7]=7;
G->arc[4][5]=26;
G->arc[5][6]=17;
G->arc[6][7]=19;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* Prim算法生成最小生成树 */
void MiniSpanTree_Prim(MGraph G){
int adjvex[MAXVEX] = {0};//保存相关顶点的下标
int lowcost[MAXVEX] = {0};//保存顶点之间的权值
//初始化lowcost数组，将v0顶点与之有边的权值存入数组，i从1开始说明已经将V0顶点加入到生成树
for(int i = 1; i<G.numVertexes; i++){
lowcost[i] = G.arc[0][i];
}
int k = 0;
int sum = 0;
for(int i = 1; i<G.numVertexes; i++){
int min = INFINITYC;
int j = 1;
while(j < G.numVertexes){
/*
1、权值为0表示已经加入到生成树中
2、找到lowcost数组中的最小权值
3、将最小权值对应的顶点赋值为k，为后面找到与顶点k有关的边做准备
*/
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;
//此时已经找到与V0顶点有边且权值最小的顶点k,遍历与K顶点有边的数组，并用权值更新lowcost数组
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);
}
int main(int argc, const char * argv[]) {
printf("Hello,最小生成树_Prim算法\n");
MGraph G;
CreateMGraph(&G);
MiniSpanTree_Prim(G);
return 0;
}
算法复杂度总结
该算法的算法复杂度为O(n2)。
三、克鲁斯卡尔算法（Kruskal算法）
算法思路
- 将邻接矩阵转化成边表数组。
- 对边表数组，根据权值大小按照从小到大进行排序。
- 遍历所有的边，通过parent数组找到边的连接信息；避免出现闭环问题。
- 如果不存在闭环，则加入到最小生成树中并修改parent数组。
算法的代码实现
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef struct Edge{
int begin;
int end;
int weight;
}Edge;
/*9.1 创建邻接矩阵*/
void CreateMGraph(MGraph *G)/* 构件图 */{
int i, j;
/* printf("请输入边数和顶点数:"); */
G->numEdges=15;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITYC;
}
}
G->arc[0][1]=10;
G->arc[0][5]=11;
G->arc[1][2]=18;
G->arc[1][8]=12;
G->arc[1][6]=16;
G->arc[2][8]=8;
G->arc[2][3]=22;
G->arc[3][8]=21;
G->arc[3][6]=24;
G->arc[3][7]=16;
G->arc[3][4]=20;
G->arc[4][7]=7;
G->arc[4][5]=26;
G->arc[5][6]=17;
G->arc[6][7]=19;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* 交换权值以及头和尾 */
void Swapn(Edge *edges,int i, int j){
Edge temp = edges[j];
edges[j].begin = edges[i].begin;
edges[j].end = edges[i].end;
edges[j].weight = edges[i].weight;
edges[i].begin = temp.begin;
edges[i].end = temp.end;
edges[i].weight = temp.weight;
}
/* 对权值进行排序 */
void sort(Edge edges[],MGraph *G){
for(int i = 0; i<G->numEdges; i++){
for(int j = i+1; j<G->numEdges; j++){
if(edges[i].weight > edges[j].weight){
Swapn(edges, i, j);
}
}
}
printf("边集数组根据权值排序之后的为:\n");
for (int i = 0; i < G->numEdges; i++)
{
printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
/* 查找连线顶点的尾部下标 */
//根据顶点f以及parent 数组,可以找到当前顶点的尾部下标; 帮助我们判断2点之间是否存在闭环问题;
int Find(int *parent, int f){
while(parent[f]){
f = parent[f];
}
return f;
}
/* 生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G){
Edge edges[MAXEDGE] = {0};
int parent[MAXEDGE] = {0};
int sum = 0;
//构建边表集
int k = 0;
for(int i = 0; i <G.numVertexes-1; i++){
for(int 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);
//计算最小生成树
printf("打印最小生成树：\n");
for (int i = 0; i < G.numEdges; i++){
//此时，若m=n则形成闭环，根据最小生成树的定义，是不允许出现闭环的，所以当出现闭环的时候应该跳过该顶点
int m = Find(parent, edges[i].begin);
int n = Find(parent, edges[i].end);
if(m!=n){
parent[m]=n;
/*打印最小生成树路径*/
printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
sum += edges[i].weight;
}
}
printf("sum = %d\n",sum);
}
int main(int argc, const char * argv[]) {
printf("Hello,最小生成树_Kruskal算法\n");
MGraph G;
CreateMGraph(&G);
MiniSpanTree_Kruskal(G);
return 0;
}
算法复杂度总结
此算法的Find函数由边数e决定，时间复杂度为O(loge)，而Find外面还有一层循环循环e次，所以总的算法复杂度为O(eloge)。
总结
对比两个算法，克鲁斯卡尔主要针对边来展开，边数少时效率会高很多，所以对于稀疏图有很大的优势。
普里姆算法对于稠密图，即边数非常多的情况会好一些。
