接下来介绍克鲁斯卡尔算法

克鲁斯卡尔算法的核心是以边为核心，不断实现“加边”的过程，和普里姆算法只是不同的两种方法，实现的结果本质是一样的。

另一种最小生成树算法普里姆算法

头文件，数据结构，定义

#include<iostream> #define Maxvexnum 10 #define MaxInt 10000 using namespace std; typedef char vertextype; typedef int arctype; int vexset[Maxvexnum]; typedef struct { vertextype vexs[Maxvexnum]; arctype arcs[Maxvexnum][Maxvexnum]; int vexnum, arcnum; struct edge; }AM_Graph; struct{ vertextype Head; vertextype Hail; arctype lowcost; }edge[Maxvexnum];

vexset[]数组表示的是连通分量，初始化为每一个顶点即为一个连通分量，edge[]表示的是每条边的两个顶点和权值。

首先我们需要对这个edge[]数组进行排序，原因在于：我们需要优先选出权值最小的边（如果构成了回路，才会选择第二小的边）

排序使用的是冒泡排序算法，需要注意的是交换的是一条边，不光只交换权值，还有首尾两个顶点。

void sort_AM(AM_Graph& g)//冒泡排序,从小到大的顺序，把最大的数放在最后一个 { int length = g.arcnum; while (length > 0) { for (int i = 0; i < length-1; i++) if (edge[i].lowcost > edge[i + 1].lowcost) { //交换数值 int exchange_lowcost = edge[i].lowcost; edge[i].lowcost = edge[i + 1].lowcost; edge[i + 1].lowcost = exchange_lowcost; //交换head char exchange_head = edge[i].Head; edge[i].Head = edge[i + 1].Head; edge[i + 1].Head = exchange_head; //交换hail char exchange_hail = edge[i].Hail; edge[i].Hail = edge[i + 1].Hail; edge[i + 1].Hail = exchange_hail; } length--; } for (int i = 0; i < g.arcnum; i++) cout << edge[i].Head << edge[i].Hail << edge[i].lowcost << endl; }

克鲁斯卡尔算法的c++实现

void minispantree_Kruskal(AM_Graph& g) { sort_AM(g); for (int i = 0; i < g.vexnum; i++) vexset[i] = i; for (int i = 0; i < g.arcnum; i++) { int v1 = LocateVex_AM(g, edge[i].Head); int v2 = LocateVex_AM(g, edge[i].Hail); int vs1 = vexset[v1]; int vs2 = vexset[v2]; if (vs1 != vs2) { cout << edge[i].Head << "-" << edge[i].Hail << endl; for (int j = 0; j < g.vexnum; j++) if (vexset[j] == vs2) vexset[j] = vs1; } } }

需要值得注意的是，如果一条边的两个点在同一连通分量上，意味着构成了回路，那么这条边就不能要，是多余的。如果不在一个连通分量上，输出这条边后，需要把这条边也放在之前的连通分量里面。