Kruskal 算法（克鲁斯卡尔算法）

大致流程

  1. 根据边权重大小排序，从小到大
  2. 并查集（初始化、merge、find）
  3. 循环条件一般为：

// 两个节点、一条边
for(int i = 0; i < connections.length; i++) {
  int a = connections[i][0];
  int b = connections[i][1];
  if(find(a) != find(b)) {
    merge(a, b);
    res += connections[i][2];
  }
}

概念

  • 重点关注：边，将边的权重按照从小到大排序（可以使用堆排）、依次将边添加，如果没有形成环则加上，如果形成环则继续判断下一条边
  • 判断是否有环：使用并查集 {
    1. init：每个元素看成一个集合
    2. find：根据祖先节点判断是否在一个集合中，如果祖先节点一致说明在同一个集合中
    3. merge：如果当前边的两个元素没有在同一个集合则将两个集合合并，如果在同一个集合说明存在环则跳过
    }
  • 时间复杂度：O(eloge)
  • 适用于稀疏图
  • 参考：Kruskal、Kruskal 算法详细


Prim 算法（普里姆算法）

  • 重点关注：点
  • 思路：{
    1. 将边的权重由小到大排序（可以使用堆排）、使用boolean[] visited 存储已经遍历过的节点，使用 result 存储结果
    2. 遍历所有节点，如果节点不在 visited，说明是新节点，将节点对应的边加入到优先队列中
    3. 遍历这个优先队列，弹出边，找到边另一头的节点，如果不在 visited中，说明是新节点，将新节点的边添加到优先队列中；
    4. 只有一个集合，可以使用 visited 来避免出现环
    }
  • 时间复杂度：O(n ^ 2)
  • 适用于稠密图
  • 参考：Prim 算法
  • 代码：
node为节点、edge为边，to、from是边对应的两个节点

Queue<Edege> queue = new PriorityQueue<>();

存储经历过的节点
Set<Node> set = new HashSet<>();

存储正确路径的边
Set<Node> result = new HashSet<>();

// 此循环处理森林问题，也就是不是全连通的；如果是全连通可以不加；
// for(Node node : graph.nodes.values()){
    if(!set.contains(node)){
        //新的节点
        set.add(node);
        for(Edge edge : node.edges){
            queue.offer(edge);
        }
        
        while(!queue.isEmpty()){
            //边的另一头的节点
            Edge edge = queue.poll();
            Node toNode = edge.to;
            
            //是新节点、添加这条边
            if(!set.contains(toNode)){
                set.add(toNode);
                result.add(edge);
                for(Edge nextEdge : toNode.edges){
                    queue.offer(nextEdge);
                }
            }
        }
    }
//}


典型题目