kruskal算法和prim算法

本文主要是介绍kruskal算法和prim算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、两种算法都针对无向图
2、目的：生成最小生成树

生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。

               一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。

最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

 相关知识参考

 一、Kruska算法

1.将图中的所有边按权值从小到大排序；
2.把图中的n个顶点看成独立的n棵树组成的森林；
3.按权值从小到大选择边，所选的边连接的两个顶点ui，vi应属于两颗不同的树，则成为最小生成树的一条边，然后将这两颗树合并作为一颗树。
4.重复（3），直到所有顶点都在一颗树内或者有n-1条边为止。

 Kruskal算法

二、prim算法 

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，

  代码实现

package Algorithms.Graph;


import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

// undirected graph only
public class Prim {

    public static class EdgeComparator implements Comparator<Edge> {

        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    }

    public static Set<Edge> primMST(Graph graph) {

        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(
                new EdgeComparator()); //优先级队列：用来存放解锁的边
        HashSet<Node> set = new HashSet<>();
        Set<Edge> result = new HashSet<>(); //用来存放依次挑选的边

        for (Node node : graph.nodes.values()) { //随便挑一个点，for循环是为了处理森林的问题
            //node是开始点                             如果一个图是连通图，就不需要for循环
            if (!set.contains(node)) {
                set.add(node);
                for (Edge edge : node.edges) { //由一个点，解锁所有相连的边
                    priorityQueue.add(edge); //把这个点所有的边放入优先级队列中
                }
                while (!priorityQueue.isEmpty()) {
                    Edge edge = priorityQueue.poll(); //从优先级队列中取一个边（value值最小的边）
                    Node toNode = edge.to;   //拿到这个边所指向的Node
                    if (!set.contains(toNode)) { // 如果这个Node不再set集合中，就是一个新Node
                        set.add(toNode);
                        result.add(edge);
                        for (Edge nextEdge : toNode.edges) { //然后再把这个新Node所有的边放入优先级队列中
                            priorityQueue.add(nextEdge);
                        }
                        //以上代码可能会把重复的边扔到优先级队列中，但不影响结果（会被if条件直接跳过）
                    }
                }
            }
        }
        return result;
    }

    // 请保证graph是连通图
    // graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路
    // 返回值是最小连通图的路径之和
    public static int prim(int[][] graph) {
        int size = graph.length;
        int[] distances = new int[size];
        boolean[] visit = new boolean[size];
        visit[0] = true;
        for (int i = 0; i < size; i++) {
            distances[i] = graph[0][i];
        }
        int sum = 0;
        for (int i = 1; i < size; i++) {
            int minPath = Integer.MAX_VALUE;
            int minIndex = -1;
            for (int j = 0; j < size; j++) {
                if (!visit[j] && distances[j] < minPath) {
                    minPath = distances[j];
                    minIndex = j;
                }
            }
            if (minIndex == -1) {
                return sum;
            }
            visit[minIndex] = true;
            sum += minPath;
            for (int j = 0; j < size; j++) {
                if (!visit[j] && distances[j] > graph[minIndex][j]) {
                    distances[j] = graph[minIndex][j];
                }
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println("hello world!");
    }

}

这篇关于kruskal算法和prim算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！