一：回顾普里姆算法
数据结构（五）图---最小生成树（普里姆算法）
普里姆算法是以某个顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树。是临时决定路径。例如：我们参观某个展会，从一个入口进入，然后我们会选择最感兴趣的场馆进入观看，看完后再用同样的方法看下一个。
二：克鲁斯卡尔算法（稀疏图）
推文：https://www.cnblogs.com/qianbixin/p/5005161.html（转载自）
例如上面参观，我们为何不先决定去看那些展馆，事先计划好，然后进园后直接按照所决定的路径进行观看。这就是克鲁斯卡尔算法的思想
注意：
克鲁斯卡尔算法需要我们了解生成树的概念，我们可以回到普里姆算法回顾下
（一）基本思想
（
1）构造一个只含n个顶点，边集为空的子图。若将图中各个顶点看成一棵树的根节点，则它是一个含有n棵树的森林。
（2）从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图。也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之
（3）依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
或者
（1）将图中的所有边都去掉。（2）将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环（3）重复上一步直到连接所有顶点，此时就生成了最小生成树。这是一种贪心策略。
（二）难点
判断某条边<u, v>的加入是否会在已经选定的边集集合中形成环。
（三）解决思路
使用并查集，分别找出两个顶点u, v所在树的根节点。若根节点相同，说明u, v在同一棵树中，则u, v连接起来会形成环；若根节点不同，则u, v不在一棵树中，连接起来不会形成环，而是将两棵树合并。
推文：数据结构（四）树---集合的表示及查找（并查集）
（四）图解过程
三：代码实现
数据结构定义
#include <stdio.h>
#include <stdlib.h>
#include <
string.h>
#include <stdbool.h>
#define MAXVEX 100
//最大顶点数
#define INFINITY 65535
//用0表示∞
typedef char VertexType;
//顶点类型，字符型A,B,C,D...
typedef
int EdgeType;
//边上权值类型10,15,...
//邻接矩阵结构
typedef
struct
{
VertexType vers[MAXVEX]; //顶点表
EdgeType arc[MAXVEX][MAXVEX];
//邻接矩阵，可看作边表
int numVertexes, numEdges;
//图中当前的顶点数和边数
}MGraph;
typedef struct
{
int begin;
int end;
int weight;
}Edge;
函数定义
//创建邻接矩阵
void CreateMGraph(MGraph*
G);
//邻接矩阵转边集数组
void MGraph2EdgeArr(MGraph G, Edge*
edge);
//显示邻接矩阵
void showGraph(MGraph G);
//找到顶点index的根节点下标返回
int Find(
int* parent,
int index);
//使用克鲁斯卡尔算法进行最小生成树的创建
void MiniSpanTree_Kruskal(MGraph G);
创建邻接矩阵
void CreateMGraph(MGraph*
G)
{
int i, j, k, w;
G->numVertexes =
9;
G->numEdges =
15;
//读入顶点信息
G->vers[
0] =
'A';
G->vers[
1] =
'B';
G->vers[
2] =
'C';
G->vers[
3] =
'D';
G->vers[
4] =
'E';
G->vers[
5] =
'F';
G->vers[
6] =
'G';
G->vers[
7] =
'H';
G->vers[
8] =
'I';
//getchar(); //可以获取回车符
for (i =
0; i < G->numVertexes; i++
)
for (j =
0; j < G->numVertexes; j++
)
G->arc[i][j] = INFINITY;
//邻接矩阵初始化
G->arc[
0][
1] =
10;
G->arc[
0][
5] =
11;
G->arc[
1][
2] =
18;
G->arc[
1][
6] =
16;
G->arc[
1][
8] =
12;
G->arc[
2][
3] =
22;
G->arc[
2][
8] =
8;
G->arc[
3][
4] =
20;
G->arc[
3][
7] =
16;
G->arc[
3][
6] =
24;
G->arc[
3][
8] =
21;
G->arc[
4][
5] =
26;
G->arc[
4][
7] =
7;
G->arc[
5][
6] =
17;
G->arc[
6][
7] =
19;
for (k =
0; k < G->numVertexes; k++)
//读入numEdges条边，建立邻接矩阵
{
for (i = k; i < G->numVertexes; i++
)
{
G->arc[i][k] = G->arc[k][i];
//因为是无向图，所有是对称矩阵
}
}
}
CreateMGraph创建邻接矩阵
邻接矩阵转边集数组
//邻接矩阵转编辑数组，按照权值排序，由小到大
void MGraph2EdgeArr(MGraph G, Edge*
edge)
{
int i, j,k=
0;
Edge temp;
int min;
for (i =
0; i < G.numVertexes;i++
)
{
for (j = i +
1; j < G.numVertexes;j++
)
{
if (G.arc[i][j]!=INFINITY)
//有边
{
edge[k].begin =
i;
edge[k].end =
j;
edge[k].weight =
G.arc[i][j];
k++
;
}
}
}
//按照冒泡大小进行排序
for (i =
0; i < k;i++
)
{
for (j = i; j < k;j++
)
{
if (edge[j].weight<
edge[i].weight)
{
temp =
edge[i];
edge[i] =
edge[j];
edge[j] =
temp;
}
}
}
}
并查集操作，获取一个顶点f的根节点下标，这里没有使用结构体，而是将数组下标作为了数据，节省了不必要空间
int Find(
int* parent,
int f)
{
while (parent[f] >
0)
f =
parent[f];
return f;
}
使用克鲁斯卡尔算法进行最小生成树的创建
void MiniSpanTree_Kruskal(MGraph G)
{
Edge edges[MAXVEX]; //定义边集数组
int parent[MAXVEX];
//定义生成树的父节点，也可以使用结构体，但是更加浪费空间
int i,n,m;
MGraph2EdgeArr(G, edges); //邻接矩阵转边集数组
//开始进行初始化
for (i =
0; i < MAXVEX; i++
)
parent[i] =
0;
//这里是0代表根节点，我们也可以使用-1，正负无穷等
//进行合并操作
for (i =
0; i < G.numEdges;i++
)
{
n = Find(parent, edges[i].begin);
//找到顶点edges[i].begin的根节点下标
m = Find(parent, edges[i].end);
//找到顶点edges[i].end的根节点位置
if (n!=m)
//若是根节点下标不是一样的，就说不在一棵树上，不会形成环，我们放心合并
{
parent[n] = m;
//将n树合并到m树，表示该边被放入生成树
printf(
"(%d,%d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
全部代码
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <
string.h>
#include <stdbool.h>
#define MAXVEX 100
//最大顶点数
#define INFINITY 65535
//用0表示∞
typedef char VertexType;
//顶点类型，字符型A,B,C,D...
typedef
int EdgeType;
//边上权值类型10,15,...
//邻接矩阵结构
typedef
struct
{
VertexType vers[MAXVEX]; //顶点表
EdgeType arc[MAXVEX][MAXVEX];
//邻接矩阵，可看作边表
int numVertexes, numEdges;
//图中当前的顶点数和边数
}MGraph;
typedef struct
{
int begin;
int end;
int weight;
}Edge;
//创建邻接矩阵
void CreateMGraph(MGraph*
G);
//邻接矩阵转边集数组
void MGraph2EdgeArr(MGraph G, Edge*
edge);
//显示邻接矩阵
void showGraph(MGraph G);
//找到顶点index的根节点下标返回
int Find(
int* parent,
int index);
//使用克鲁斯卡尔算法进行最小生成树的创建
void MiniSpanTree_Kruskal(MGraph G);
int main()
{
MGraph MG;
CreateMGraph(&
MG);
showGraph(MG);
MiniSpanTree_Kruskal(MG);
system("pause");
return 0;
}
//生成邻接矩阵
void CreateMGraph(MGraph*
G)
{
int i, j, k, w;
G->numVertexes =
9;
G->numEdges =
15;
//读入顶点信息
G->vers[
0] =
'A';
G->vers[
1] =
'B';
G->vers[
2] =
'C';
G->vers[
3] =
'D';
G->vers[
4] =
'E';
G->vers[
5] =
'F';
G->vers[
6] =
'G';
G->vers[
7] =
'H';
G->vers[
8] =
'I';
//getchar(); //可以获取回车符
for (i =
0; i < G->numVertexes; i++
)
for (j =
0; j < G->numVertexes; j++
)
G->arc[i][j] = INFINITY;
//邻接矩阵初始化
G->arc[
0][
1] =
10;
G->arc[
0][
5] =
11;
G->arc[
1][
2] =
18;
G->arc[
1][
6] =
16;
G->arc[
1][
8] =
12;
G->arc[
2][
3] =
22;
G->arc[
2][
8] =
8;
G->arc[
3][
4] =
20;
G->arc[
3][
7] =
16;
G->arc[
3][
6] =
24;
G->arc[
3][
8] =
21;
G->arc[
4][
5] =
26;
G->arc[
4][
7] =
7;
G->arc[
5][
6] =
17;
G->arc[
6][
7] =
19;
for (k =
0; k < G->numVertexes; k++)
//读入numEdges条边，建立邻接矩阵
{
for (i = k; i < G->numVertexes; i++
)
{
G->arc[i][k] = G->arc[k][i];
//因为是无向图，所有是对称矩阵
}
}
}
//邻接矩阵转编辑数组，按照权值排序，由小到大
void MGraph2EdgeArr(MGraph G, Edge*
edge)
{
int i, j,k=
0;
Edge temp;
int min;
for (i =
0; i < G.numVertexes;i++
)
{
for (j = i +
1; j < G.numVertexes;j++
)
{
if (G.arc[i][j]!=INFINITY)
//有边
{
edge[k].begin =
i;
edge[k].end =
j;
edge[k].weight =
G.arc[i][j];
k++
;
}
}
}
//按照冒泡大小进行排序
for (i =
0; i < k;i++
)
{
for (j = i; j < k;j++
)
{
if (edge[j].weight<
edge[i].weight)
{
temp =
edge[i];
edge[i] =
edge[j];
edge[j] =
temp;
}
}
}
}
//显示邻接矩阵
void showGraph(MGraph G)
{
for (
int i =
0; i < G.numVertexes; i++
)
{
for (
int j =
0; j < G.numVertexes; j++
)
{
if (G.arc[i][j] !=
INFINITY)
printf("]", G.arc[i][j]);
else
printf(" 0");
}
printf("\n");
}
}
//并查集操作，获取一个顶点f的根节点下标
int Find(
int* parent,
int f)
{
while (parent[f] >
0)
f =
parent[f];
return f;
}
//使用克鲁斯卡尔算法进行最小生成树的创建
void MiniSpanTree_Kruskal(MGraph G)
{
Edge edges[MAXVEX]; //定义边集数组
int parent[MAXVEX];
//定义生成树的父节点，也可以使用结构体，但是更加浪费空间
int i, n, m;
MGraph2EdgeArr(G, edges); //邻接矩阵转边集数组
//开始进行初始化
for (i =
0; i < MAXVEX; i++
)
parent[i] =
0;
//这里是0代表根节点，我们也可以使用-1，正负无穷等
//进行合并操作
for (i =
0; i < G.numEdges; i++
)
{
n = Find(parent, edges[i].begin);
//找到顶点edges[i].begin的根节点下标
m = Find(parent, edges[i].end);
//找到顶点edges[i].end的根节点位置
if (n != m)
//若是根节点下标不是一样的，就说不在一棵树上，不会形成环，我们放心合并
{
parent[n] = m;
//将n树合并到m树，表示该边被放入生成树
printf(
"(%d,%d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
View Code
四：总结
将图中各边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边, 若形成回路则除去.依次选够(n-
1)条边,即得最小生成树.(n为顶点数)
克鲁斯卡尔算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。（若图的顶点数为n，边数为e）。
转载于:https://www.cnblogs.com/ssyfj/p/9488850.html
