图的最小生成树-克鲁斯卡尔算法
一、基本概念
生成树：一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。
最小生成树：把构造连通网的最小代价生成树称为最小生成树。（一棵生成树的代价就是树上各边的代价之和）。
二、经典算法
克鲁斯卡尔算法（主要针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势）
1、主要思路，如下图所示：
按权值递增的顺序将连接了两棵树的边 (0，2)，(3，5)，(1，4)，(2，5) 依次改为红边，加入 T 中。
由于边 (0，3) 的两个顶点在相同的一棵树上，所以舍去。而边 (2，4) 和 (1，2) 的长度相同，可以任选其中一条加入。
如上图所示，红色连接的部分就是生成的最小生成树。
2、算法实现
/**
* 实验题目:
* 采用克鲁斯卡尔算法求最小生成树
* 实验目的:
* 领会克鲁斯卡尔算法求带权连通图中最小生成树的过程和相关算法设计
* 实验内容:
* 编写程序，实现求带权连通图最小生成树的克鲁斯卡尔算法。对于如下
* 图所示的带权连通图，输出从顶点0出发的一颗最小生成树。
*/
#include <stdio.h>
#include <malloc.h>
#define INF 32767 //定义∞
#define MAXV 100 //最大顶点个数
typedef char InfoType;
/*-------------------------以下定义邻接矩阵类型---------------------------*/
typedef struct
{
int no; //顶点编号
InfoType info; //顶点信息
}VertexType; //顶点类型
typedef struct
{
int edges[MAXV][MAXV]; //邻接矩阵数组(用一个二维数组存放顶点间关系(边或弧)的数据)
int n; //顶点数
int e; //边数
VertexType vexs[MAXV]; //存放顶点信息(用一个一维数组存放图中所有顶点数据)
}MatGraph; //完整的图邻接矩阵类型
//邻接表表示法-将每个顶点的邻接点串成一个单链表
/*-----------以下定义邻接表类型--------------*/
typedef struct ArcNode
{
int adjvex; //该边的邻接点编号
struct ArcNode *nextarc; //指向下一条边的指针
int weight; //该边的相关信息,如权值(用整型表示)
}ArcNode; //边结点类型
typedef struct VNode
{
InfoType info; //顶点其他信息
int cnt; //存放顶点入度,仅用于拓扑排序
ArcNode *firstarc; //指向第一条边
}VNode; //邻接表结点类型
typedef struct
{
VNode adjlist[MAXV]; //邻接表头结点数组
int n; //图中顶点数
int e; //图中边数
}AdjGraph; //完整的图邻接表类型
/*-------------------------邻接矩阵的基本运算算法---------------------------*/
/*------------由边数组A、顶点数n和边数e创建图的邻接矩阵g--------------------*/
void CreateMat(MatGraph &g, int A[MAXV][MAXV], int n, int e)
{
int i, j;
g.n = n;
g.e = e;
for(i = 0; i < g.n; i++)
for(j = 0; j < g.n; j++)
g.edges[i][j] = A[i][j];
}
/*------------输出邻接矩阵g--------------------*/
void DispMat(MatGraph g)
{
int i, j;
for(i = 0; i < g.n; i++)
{
for(j = 0; j < g.n; j++)
{
if(g.edges[i][j] != INF)
printf("%4d", g.edges[i][j]);
else
printf("%4s", "∞");
}
printf("\n");
}
}
/*-------------------------邻接表的基本运算算法---------------------------*/
/*-------------------由边数组A、顶点数n和边数e创建图的邻接表G--------------------*/
void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
{
int i, j;
ArcNode *p;
G = (AdjGraph *)malloc(sizeof(AdjGraph));
for(i = 0; i < n; i++) //给邻接表中所有头结点的指针域置初值NULL
{
G->adjlist[i].firstarc = NULL;
}
for(i = 0; i < n; i++) //检查邻接矩阵中的每个元素
{
for(j = n - 1; j >= 0; j--)
{
if(A[i][j] != 0 && A[i][j] != INF) //存在一条边
{
p = (ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点p
p->adjvex = j; //邻接点编号
p->weight = A[i][j]; //边的权重
p->nextarc = G->adjlist[i].firstarc; //采用头插法插入结点p
G->adjlist[i].firstarc = p;
}
}
}
G->n = n;
G->e = e;
}
/*-------------------输出邻接表G--------------------*/
void DispAdj(AdjGraph *G)
{
ArcNode *p;
for(int i = 0; i < G->n; i++)
{
p = G->adjlist[i].firstarc;
printf("%d: ", i);
while(p != NULL)
{
printf("%3d[%d]->", p->adjvex, p->weight); //邻接点编号[权重]
p = p->nextarc;
}
printf("∧\n");
}
}
/*-------------------销毁图的邻接表G--------------------*/
void DestroyAdj(AdjGraph *&G)
{
ArcNode *pre, *p;
for(int i = 0; i < G->n; i++)
{
pre = G->adjlist[i].firstarc; //pre指向第i个单链表的首结点
if(pre != NULL)
{
p = pre->nextarc;
while(p != NULL) //释放第i个单链表的所有边结点
{
free(pre);
pre = p;
p = p->nextarc;
}
free(pre);
}
}
free(G); //释放头结点数组
}
#define MAX_SIZE 100
typedef struct Edge
{
int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
}Edge;
/**
* 功能:
* 采用直接插入排序方法对E[0...n-1]按权值w递增排序
* 边(1, 0) = 5 0 j
* 边(2, 0) = 8 1
* 边(2, 1) = 4 2 i
* 边(3, 0) = 7 3
* 边(3, 2) = 5 4
* 边(4, 3) = 5 5
* 边(5, 0) = 3 6
* 边(5, 2) = 9 7
* 边(5, 3) = 6 8
* 边(5, 4) = 1 9
*/
void insert_sort(Edge E[], int e)
{
int i, j;
Edge temp;
for(i = 1; i < e; i++)
{
temp = E[i];
j = i - 1;
while(j >= 0 && temp.w < E[j].w)
{
E[j + 1] = E[j];
j--;
}
E[j + 1] = temp;
}
}
/**
* 功能:
* 采用克鲁斯卡尔算法输出图g的一棵最小生成树(n个顶点，n-1条边)
*/
void Kruskal(MatGraph g)
{
int u1, v1;
int sn1, sn2;
int i, j;
int k;
Edge E[MAX_SIZE]; //存放所有边
int vset[MAXV];
k = 0; //E数组的下标从0开始计
printf("图g边集合:\n");
for(i = 0; i < g.n; i++) //由g产生的边集E
{
for(j = 0; j <= i; j++)
{
if(g.edges[i][j] != 0 && g.edges[i][j] != INF)
{
E[k].u = i;
E[k].v = j;
E[k].w = g.edges[i][j];
k++;
printf(" 边(%d, %d) = %d\n", i, j, g.edges[i][j]);
}
}
}
insert_sort(E, g.e); //采用直接插入排序方法对E[0...n-1]按权值w递增排序
printf("图g边集合按权值w递增排序后:\n");
for(i = 0; i < g.e; i++)
{
printf(" 边(%d, %d) = %d\n", E[i].u, E[i].v, E[i].w);
}
printf("图全部顶点集合vset = { ");
for(i = 0; i < g.n; i++) //初始化辅助数组
{
vset[i] = i;
printf("%d ", vset[i]);
}
printf("}\n");
k = 1; //k表示当前构造生成树的第几条边,初值为1
j = 0; //E中边的下标,初值为0
while(k < g.n) //生成的边数小于顶点个数n时循环
{
u1 = E[j].u; //取一条边的起始顶点和终止顶点
v1 = E[j].v;
sn1 = vset[u1];
sn2 = vset[v1]; //分别得到两个顶点所属的集合编号
printf(" 起始顶点u1 = %d所属集合编号sn1 = %d, 终止顶点v1 = %d所属集合编号sn2 = %d\n", u1, sn1, v1, sn2);
if(sn1 != sn2)
{
printf(" 图g最小生成树的边(%d,%d) = %d\n", u1, v1, E[j].w);
k++; //生成边数增1
for(i = 0; i < g.n; i++) //两个集合统一编号
{
if(vset[i] == sn2) //集合编号为sn2的改为sn1
{
vset[i] = sn1;
}
}
}
j++; //扫描下一条边
}
}
int main(void)
{
MatGraph g;
int n = 6;
int e = 10;
int A[MAXV][MAXV] = {
{0, 5, 8, 7, INF, 3},
{5, 0, 4, INF, INF, INF},
{8, 4, 0, 5, INF, 9},
{7, INF, 5, 0, 5, 6},
{INF, INF, INF, 5, 0, 1},
{3, INF, 9, 6, 1, 0}
};
CreateMat(g, A, n, e); //创建图的邻接矩阵
printf("图G的邻接矩阵:\n");
DispMat(g);
printf("克鲁斯卡尔算法求解最小生成树:\n");
Kruskal(g);
return 0;
}
输出结果:
图G的邻接矩阵:
0 5 8 7 ∞ 3
5 0 4 ∞ ∞ ∞
8 4 0 5 ∞ 9
7 ∞ 5 0 5 6
∞ ∞ ∞ 5 0 1
3 ∞ 9 6 1 0
克鲁斯卡尔算法求解最小生成树:
图g边集合:
边(1, 0) = 5
边(2, 0) = 8
边(2, 1) = 4
边(3, 0) = 7
边(3, 2) = 5
边(4, 3) = 5
边(5, 0) = 3
边(5, 2) = 9
边(5, 3) = 6
边(5, 4) = 1
图g边集合按权值w递增排序后:
边(5, 4) = 1
边(5, 0) = 3
边(2, 1) = 4
边(1, 0) = 5
边(3, 2) = 5
边(4, 3) = 5
边(5, 3) = 6
边(3, 0) = 7
边(2, 0) = 8
边(5, 2) = 9
图全部顶点集合vset = { 0 1 2 3 4 5 }
起始顶点u1 = 5所属集合编号sn1 = 5, 终止顶点v1 = 4所属集合编号sn2 = 4
图g最小生成树的边(5,4) = 1
起始顶点u1 = 5所属集合编号sn1 = 5, 终止顶点v1 = 0所属集合编号sn2 = 0
图g最小生成树的边(5,0) = 3
起始顶点u1 = 2所属集合编号sn1 = 2, 终止顶点v1 = 1所属集合编号sn2 = 1
图g最小生成树的边(2,1) = 4
起始顶点u1 = 1所属集合编号sn1 = 2, 终止顶点v1 = 0所属集合编号sn2 = 5
图g最小生成树的边(1,0) = 5
起始顶点u1 = 3所属集合编号sn1 = 3, 终止顶点v1 = 2所属集合编号sn2 = 2
图g最小生成树的边(3,2) = 5