1.算法描述
克鲁斯卡尔算法需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系，可以证明其时间复杂度为O（eloge）。
2.算法思想
1.将图各边按照权值进行排序
2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。
3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应为n-1条），算法结束。得到的就是此图的最小生成树。
3.JAVA代码
1)结构体定义
// 边的结构体
class ENode {
char start; // 边的起点
char end; // 边的终点
int weight; // 边的权重
public ENode(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
};
// 邻接表中表的顶点
class VNode {
char data; // 顶点信息
ENode firstEdge; // 指向第一条依附该顶点的弧
};
class Graph {
private static final int INF = Integer.MAX_VALUE; // 最大值
char[] vertexs; // 顶点集合
int[][] matrix; // 邻接矩阵
// 得到当前有向图中的所有边信息
public List<ENode> getEdges() {
List<ENode> edges = new ArrayList<ENode>();
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
if (matrix[i][j] != INF) {
ENode edge = new ENode(vertexs[i], vertexs[j], matrix[i][j]);
edges.add(edge);
}
}
}
return edges;
}
}
2)kruskal算法
private static final int INF = Integer.MAX_VALUE; // 最大值
static void qSort(List<ENode> edges, int low, int high) {
if (low < high) {
int i = low, j = high;
ENode edge = edges.get(low);
while (i < j) {
while (edge.weight < edges.get(j).weight && i < j)
j--;
edges.set(i, edges.get(j));
while (edge.weight > edges.get(i).weight && i < j)
i++;
edges.set(j, edges.get(j));
}
edges.set(i, edge);
qSort(edges, low, i - 1);
qSort(edges, i + 1, high);
}
}
public static void kruskal(Graph G) {
// 1.拿到有向图中所有边
List<ENode> edges = G.getEdges();
int edgeNum = edges.size();
// 2.对所有有向边进行排序
qSort(edges, 0, edgeNum - 1);
ENode[] minTree = new ENode[G.vertexs.length - 1]; // 结果数组，保存kruskal最小生成树的边
int index = 0; // minTree数组的索引
// 用于保存"已有最小生成树"中每个顶点（以数组下标表示） 与 其经过“最短边”的邻接顶点 （以对应下标的值表示）的并查集
int[] start2end = new int[G.vertexs.length];
// 3.依次将最短且不与T构成回路的边加入T集合
for (int i = 0; i < edgeNum; i++) {
//得到当前最短边 在有向图G中的起始顶点与终结顶点的 下标
int p1 = getIndex(G, edges.get(i).start); // 获取第i条边的"起点"的序号
int p2 = getIndex(G, edges.get(i).end); // 获取第i条边的"终点"的序号
//分别得到在T集合中沿当前最短边的“起点”与“终点”遍历到的最后节点，
//若加入当前最短边后T集合存在回路，则“起点”与“终点”遍历到的最后节点一定是同一节点
int m = getEnd(start2end, p1); // 获取p1在"已有的最小生成树"中的终点
int n = getEnd(start2end, p2); // 获取p2在"已有的最小生成树"中的终点
//当前最短边加入T集合后没有有回路 则将当前最短边加入T集合，并且记录当前最短边的“起点”与“终点”
if (m != n) {
start2end[m] = n; // “起点”即vends的数组下标与“终点”即vends的对应下标的值
minTree[index++] = edges.get(i); // 保存结果
}
}
}
static int getIndex(Graph G, char ch) {
int i = 0;
for (; i < G.vertexs.length; i++)
if (G.vertexs[i] == ch)
return i;
return -1;
}
static int getEnd(int start2end[], int i) {
while (start2end[i] != 0)
i = start2end[i];
return i;
}
