用 java语言以测试驱动开发实现Prim 和 Kruskal 算法

对于Prim算法，我们可以采用以下步骤：

1. 创建一个PriorityQueue来存储边，按照边的权重从小到大排序。
2. 创建一个HashSet来存储已经访问过的节点。
3. 从任意一个节点开始，将该节点添加到HashSet中。
4. 对于该节点的所有邻居节点，将与其相连的边添加到PriorityQueue中。
5. 从PriorityQueue中弹出最小的边，如果该边的两个节点都没有被访问过，则将该边加入到最小生成树中，并将该边的两个节点加入到HashSet中。
6. 重复步骤4和步骤5，直到PriorityQueue为空。

下面是Prim算法的Java代码：

import java.util.*;

public class Prim {
    public static List<Edge> primMST(Graph g) {
        List<Edge> mst = new ArrayList<>();
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        Set<Integer> visited = new HashSet<>();

        int startNode = g.nodes.keySet().iterator().next();
        visited.add(startNode);

        while (visited.size() < g.nodes.size()) {
            for (Edge e : g.nodes.get(startNode).edges) {
                if (!visited.contains(e.to)) {
                    pq.offer(e);
                }
            }

            Edge minEdge = pq.poll();
            if (minEdge != null) {
                mst.add(minEdge);
                startNode = minEdge.to;
                visited.add(startNode);
            }
        }

        return mst;
    }
}

class Graph {
    Map<Integer, Node> nodes = new HashMap<>();
}

class Node {
    int id;
    List<Edge> edges = new ArrayList<>();
}

class Edge implements Comparable<Edge> {
    int from;
    int to;
    int weight;

    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(weight, other.weight);
    }
}

对于Kruskal算法，我们可以采用以下步骤：

1. 创建一个PriorityQueue来存储边，按照边的权重从小到大排序。
2. 创建一个并查集，用于判断两个节点是否在同一个连通块中。
3. 将所有边加入到PriorityQueue中。
4. 从PriorityQueue中弹出最小的边，如果该边的两个节点不在同一个连通块中，则将该边加入到最小生成树中，并将这两个节点合并到同一个连通块中。
5. 重复步骤4，直到PriorityQueue为空或者最小生成树的边数达到节点数减1。

下面是Kruskal算法的Java代码：

import java.util.*;

public class Kruskal {
    public static List<Edge> kruskalMST(Graph g) {
        List<Edge> mst = new ArrayList<>();
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        UnionFind uf = new UnionFind(g.nodes.keySet());

        for (Node node : g.nodes.values()) {
            pq.addAll(node.edges);
        }

        while (!pq.isEmpty() && mst.size() < g.nodes.size() - 1) {
            Edge minEdge = pq.poll();
            if (!uf.connected(minEdge.from, minEdge.to)) {
                mst.add(minEdge);
                uf.union(minEdge.from, minEdge.to);
            }
        }

        return mst;
    }
}

class UnionFind {
    Map<Integer, Integer> parent = new HashMap<>();

    public UnionFind(Set<Integer> nodes) {
        for (int node : nodes) {
            parent.put(node, node);
        }
    }

    public int find(int p) {
        while (p != parent.get(p)) {
            parent.put(p, parent.get(parent.get(p)));
            p = parent.get(p);
        }
        return p;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        parent.put(rootP, rootQ);
    }
}

class Graph {
    Map<Integer, Node> nodes = new HashMap<>();
}

class Node {
    int id;
    List<Edge> edges = new ArrayList<>();
}

class Edge implements Comparable<Edge> {
    int from;
    int to;
    int weight;

    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(weight, other.weight);
    }
}