Kruskal
- 加边式： 每次都加入 连接了两个联通子图的、当前可选择w最小的##边##
- 每次按照权重由小->大遍历边，当边的两个定点位于两个连通图时，最小生成树可以纳入这条边，并且从候选集删除
- 时间复杂度：e*loge (e为图中的边数) 排序的时间
/**
* 克鲁斯卡尔算法-最小生成树
*
* @return void
*/
public class Graph<T> {
private int N; // N个节点
public int[][] matrix; // 邻接矩阵
private T[] datas; // 保存每个节点的数据
public List<Edge> edges = new ArrayList<>();
class Edge {
int A; // 顶点索引
int B; // 顶点索引
public Edge(int a, int b) {
A = a;
B = b;
}
@Override
public String toString() {
return "<" +
datas[A] +
"-" + matrix[A][B] + "-" + datas[B] +
'>';
}
}
}
public void KruskalTree() {
// ends保存取出各个边后依次拼接时, 各个顶点的终点索引
int[] ends = new int[N];
// 把边的权重排序
edges.sort(new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return matrix[o1.A][o1.B] - matrix[o2.A][o2.B];
}
});
// 保存最终结果的所有边的集合
List<Edge> result = new ArrayList<>();
// 依次取出并拼接
for (Edge edge : edges) {
// 如果这条边取出来拼接后构成环, 则取消拼接操作
int endOfA = getEnd(ends, edge.A);
int endOfB = getEnd(ends, edge.B);
// 如果边的第一个顶点的终点不等于第二个顶点的终点
if (endOfA != endOfB) {
// 设置第一个顶点的终点的终点为第二个顶点的终点
ends[endOfA] = endOfB;
result.add(edge);
}
}
// 查看一下结果
System.out.println(result);
// 返回最小生成树的邻接矩阵
int[][] treeMatrix = new int[N][N];
// 将结果集合的所有边以邻接矩阵的形式表现
for (Edge edge : result) {
treeMatrix[edge.A][edge.B] = matrix[edge.A][edge.B];
}
System.out.println("最小生成树的邻接矩阵: ");
for (int[] nums : treeMatrix) {
System.out.println(Arrays.toString(nums));
}
}
/**
* 本方法获取索引为i的顶点的终点, 用于判断两个顶点的终点是否相同
*
* @param ends 记录各个顶点的终点(遍历过程中才动态确定的数组)
* @param i 传入的顶点索引
* @return int 传入索引对应顶点的终点索引
*/
private int getEnd(int[] ends, int i) {
while (ends[i] != 0) { // 循环是为了找到最终的终点
i = ends[i];
}
return i;
}
Prim
- 加点式
- 维护两个列表：
- 每个V-S中的节点，到S中节点的最短距离
- 每个V-S中的节点，到S中距离最短的上一个跳板节点
- 时间复杂度（顶点数v，边数e）
- 邻接矩阵:O(v^2)
- 邻接表:O(e*logv)
import java.util.Scanner;
public class PrimMST {
private static int MAX = 100;
private static int[][] graph = new int[MAX][MAX];
private int[] lowcost = new int[MAX];// 标志所在的集合
private int[] mst = new int[MAX];//
private static int INFINITY = 99999999;// 定义无穷大
private int mincost = 0;// 最小成本
private static int mstcost = 0;// 最小成本
private static int n;// 结点个数
private int middle;// 中间结点
private int sum = 0;
public static void main(String args[]) {
PrimMST sp = new PrimMST();
sp.init();
mstcost = sp.prim(graph, n);
System.out.println("最小生成树权值和为：" + mstcost);
}
// 初始化
public void init() {
Scanner scan = new Scanner(System.in);
int p, q, w;
System.out.println("spanning tree begin!Input the node number:");
n = scan.nextInt();
System.out.println("Input the graph(-1,-1,-1 to exit)");
while (true) {
p = scan.nextInt();
q = scan.nextInt();
w = scan.nextInt();
if (p < 0 || q < 0 || w < 0) {
break;
}
graph[p][q] = w;
graph[q][p] = w;
}
scan.close();
}
// prim算法主体
public int prim(int graph[][], int n) {
for (int i = 2; i <= n; i++) {
lowcost[i] = graph[1][i];
mst[i] = 1;
}
mst[1] = 0;
for (int i = 2; i <= n; i++) {
mincost = INFINITY;
middle = 0;
for (int j = 0; j <= n; j++) {
if (lowcost[j] < mincost && lowcost[j] != 0) {
mincost = lowcost[j];
middle = j;
}
}
System.out.println(mst[middle] + "--" + middle + "==" + mincost);
sum += mincost;
lowcost[middle] = 0;
for (int j = 0; j <= n; j++) {
if (graph[middle][j] < lowcost[j]) {
lowcost[j] = graph[middle][j];
mst[j] = middle;
}
}
}
return sum;
}
}
