最小生成树问题

问题描述

• 设G=(V,E）是无向连通带权图，即一个网络，E中每条边（V,W）的权为c[v][w]，如果G的一个子图G’是一颗包含G的所有顶点的树，则称G’为G的生成树，生成树上各边权的总和称为该生成树的耗费，在G的所有生成树中，耗费最小的生成树称为G的最小生成树。

Prim算法

算法分析

• 设G=(V,E）是联通带权图，V={1,2,…,n}
• 构造G的最小生成树Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就做如下的贪心选择。
  • 选取满足条件，i∈S,j∈V-S，且c[i][j]最小的边，并将顶点j添加到S中，这个过程一直进行到S=V时为止，在这个过程中选取到的所有边恰好构成G的一颗最小生成树。

代码实现

public class Prim {

    static int maxint = Integer.MAX_VALUE;
    static int inf = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int n = 6;
        int[][] c = new int[n][n];
        c[0] = new int[]{0, 6, 1, 5, maxint, maxint};
        c[1] = new int[]{6, 0, 5, maxint, 3, maxint};
        c[2] = new int[]{1, 5, 0, 5, 6, 4};
        c[3] = new int[]{5, maxint, 5, 0, maxint, 2};
        c[4] = new int[]{maxint, 3, 6, maxint, 0, 6};
        c[5] = new int[]{maxint, maxint, 4, 2, 6, 0};
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < c[i].length; j++) {
                if (c[i][j] == Integer.MAX_VALUE) {
                    System.out.printf("  inf");
                } else {
                    System.out.printf("%5d", c[i][j]);
                }
            }
            System.out.println();
        }
        Prim(n, c);
    }

    public static void Prim(int n, int[][] c) {
        int[] lowcost = new int[n];
        int[] closest = new int[n];
        boolean[] s = new boolean[n];
        s[0] = true;
        // 初始化节点1
        for (int i = 0; i < n; i++) {
            lowcost[i] = c[0][i];
            closest[i] = 0;
            s[i] = false;
        }
        System.out.println("初始节点：" + 1);
        // 循环n-1次，每次选中一个最短路径的节点。
        for (int i = 0; i < n - 1; i++) {
            int min = inf;
            int j = 0;
            // 选出最短路径的节点。
            for (int k = 1; k < n; k++) {
                if ((lowcost[k] < min) && (!s[k])) {
                    min = lowcost[k];
                    j = k;
                }
            }
            System.out.println("当前节点：" + (j + 1) + "  选边：" + (closest[j] + 1) + "---" + (j + 1));
            s[j] = true;
            // 将选出的节点到其他未被选中的节点之间的距离与原本的lowcost做比较，存储较小的。
            for (int k = 1; k < n; k++) {
                if ((c[j][k] < lowcost[k]) && (!s[k])) {
                    lowcost[k] = c[j][k];
                    closest[k] = j;
                }
            }
        }
    }

}

• Prim(int n, int[][] c)：计算最小生成树。
  • int n：节点的数目。
  • int[][] c：输入连通带权图。

Kruskal算法

算法分析

• 将图中所有边按权重从小到大排序，假设放在集合G当中，结合S放即将构成最小生成树所选的边，刚开始时，结合S为空集。
• 逐渐选取权重最小的边，若此边与已经已经选中的边没有构成环，则放进S集合中。
• 重复第三步，直至S集合中的边的数量等于集合G的顶点数-1

代码实现

public class Kruskal {

    public static void main(String[] args) {
        // 给定边的数量和顶点的数量。
        int vertices_num = 10;
        int edges_num = 6;
        //new一个Graph对象。
        Graph graph = new Graph(vertices_num, edges_num);
        // 新建edges_num个Edge对象。
        List<Edge> edge = new ArrayList<>();
        edge.add(new Edge(1, 2, 6));
        edge.add(new Edge(1, 3, 1));
        edge.add(new Edge(1, 4, 5));
        edge.add(new Edge(2, 3, 5));
        edge.add(new Edge(2, 5, 3));
        edge.add(new Edge(3, 4, 5));
        edge.add(new Edge(3, 5, 6));
        edge.add(new Edge(3, 6, 4));
        edge.add(new Edge(4, 6, 2));
        edge.add(new Edge(5, 6, 6));
        // 将边加载到图中。
        graph.setEdge(edge);
        // 对图中的边按照权重进行排序，返回该图边的数组。
        Edge[] arrEdges = graph.sort();
        System.out.println(Arrays.toString(arrEdges));
        // 定义represent数组来记录每个顶点属于那个集合的"代表元素";
        int[] represent = new int[edges_num + 1];
        // 首先我们将这些集合的代表元素初始化为 -1，表示他们都是单个元素的集合。
        Arrays.fill(represent, -1);
        graph = findMST(graph, arrEdges, represent);
        System.out.println("最小生成树为：\n" + graph);
    }

    /**
     * @param graph     原图。
     * @param arrEdges  图中所有排序后的边按升序构成的数组。
     * @param represent 图中顶点的"代表元素”
     */
    private static Graph findMST(Graph graph, Edge[] arrEdges, int[] represent) {
        //edgesMST用来保存图中最小生成树的所包含的边。
        List<Edge> edgeList = new ArrayList<>();
        //new一个Graph实例来保存最小生成树。
        Graph graphMST = new Graph();
        //for循环限制条件中的edgeList.size()<graph.getVertices_number(）是因为MST中的边的条数等于顶点的个数减一。
        for (int i = 0; i < graph.getEdges_number() && edgeList.size() < graph.getVertices_number(); i++) {
            // 将这条边加入到最小生成树中进行判断。
            edgeList.add(arrEdges[i]);
            System.out.println((i + 1) + "：打印edgeList:\n" + edgeList);
            // 借用一个中间图，每次只传入新的边，然后配合原来的represent来判断是否构成环。
            Graph graphTemp = new Graph();
            List<Edge> tempEdge = new ArrayList<>();
            tempEdge.add(arrEdges[i]);
            graphTemp.setEdge(tempEdge);
            if (DisjuntSetCircle.isCycle(graphTemp, represent)) {
                System.out.println("第" + (i + 1) + "次有环");
                // 如果构成环，则去掉刚刚加进来的这条边。
                edgeList.remove(arrEdges[i]);
            }
            // 不断更新MST中的边的内容。
            graphMST.setEdge(edgeList);
        }
        return graphMST;
    }
}

class Edge implements Comparable<Edge> {
    // 边的始点。
    private int src;
    // 边的终点。
    private int dest;
    // 边的权重。
    private int weight;

    public Edge(int src, int dest, int weight) {
        super();
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    public int getSrc() {
        return src;
    }

    public void setSrc(int src) {
        this.src = src;
    }

    public int getDest() {
        return dest;
    }

    public void setDest(int dest) {
        this.dest = dest;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        // TODO Auto-generated method stub
        if (this.weight < o.weight)
            return -1;
        else if (this.weight > o.weight)
            return 1;
        else
            return 0;
    }

    public String toString() {
        return "(" + src + "---" + dest + " :" + weight + ")";
    }
}


class Graph {
    // 图中的顶点的个数。
    private int vertices_number;
    // 图中的边的个数。
    private int edges_number;
    // 图中边对象的引用。
    private List<Edge> edges;

    public Graph() {

    }

    public Graph(int vertices_number, int edges_number) {
        super();
        this.vertices_number = vertices_number;
        this.edges_number = edges_number;
    }

    public int getVertices_number() {
        return vertices_number;
    }

    public void setVertices_number(int vertices_number) {
        this.vertices_number = vertices_number;
    }

    public int getEdges_number() {
        return edges_number;
    }

    public void setEdges_number(int edges_number) {
        this.edges_number = edges_number;
    }

    public List<Edge> getEdge() {
        return edges;
    }

    public void setEdge(List<Edge> edge) {
        this.edges = edge;
    }

    // 功能：对图中的所有边按照边的权重按照从小到大的排序
    public Edge[] sort() {
        Edge[] arrayEdge = new Edge[edges.size()];
        for (int i = 0; i < edges.size(); i++) {
            arrayEdge[i] = edges.get(i);
        }
        Arrays.sort(arrayEdge);
        return arrayEdge;

    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        for (Edge edge : edges) {
            sb.append("(").append(edge.getSrc()).append("---").append(edge.getDest()).append(" :").append(edge.getWeight()).append(")").append("\n");

        }
        return new String(sb);
    }


}

/**
 * 返回true是有环的，返回false是没有环的。
 */
class DisjuntSetCircle {

    public static boolean isCycle(Graph graph, int[] represent) {
        int num = graph.getEdge().size();
        int src_represent;
        int dest_represent;
        for (int i = 0; i < num; i++) {
            // 得到边的起始点。
            int src = graph.getEdge().get(i).getSrc();
            // 得到边的终点。
            int dest = graph.getEdge().get(i).getDest();
            src_represent = find(represent, src);
            dest_represent = find(represent, dest);
            // 说明，边的两个顶点已经出现在了集合中，加上此边之后，构成"环"
            if (src_represent == dest_represent) {
                return true;
                // 否则，合并。
            } else {
                union(represent, src_represent, dest_represent);
            }
            System.out.println("-------represent-------");
            for (int j = 1; j < represent.length; j++) {
                System.out.println(j + ": rep:" + represent[j]);
            }
        }
        return false;
    }

    // 合并两个不相交的集合。
    private static void union(int[] represent, int src_represent, int dest_represent) {
        // 由于两者是两个集合的不同的"代表元素"，因此将其中的的"代表元素”改为另外一个即可完成合并。
        represent[src_represent] = dest_represent;
    }

    // 用来寻找顶点X所在集合的"代表元素"
    private static int find(int[] represent, int x) {
        /*
         * 首先判断顶点x的"代表元素是不是等于-1"，若等于-1，则说明，其实一个顶点的集合，返回自身顶点的标号即可。
         * 若不等于-1，则说明此点在某个集合中，我们需找到他的代表元素的标号，即我们需要向上查找。
         */
        if (represent[x] == -1) {
            return x;
        }
        return find(represent, represent[x]);
    }

}

• findMST(Graph graph, Edge[] arrEdges, int[] represent)：寻找最小生成树。
  • Graph graph：输入待处理的图。
  • Edge[] arrEdges：按权值由小到大排序后的所有边。
  • int[] represent：代表数组。
  • return Graph graphMST：得出的最小生成树。
• DisjuntSetCircle.Class
  • isCycle(Graph graph, int[] represent)：判断一个图是否成环。
    • Graph graph：输入待判断的图。
    • int[] represent：代表数组。
  • union(int[] represent, int src_represent, int dest_represent)：合并两个不相交的集合。
    • int[] represent：代表数组。
    • int src_represent：代表元素的起点。
    • int dest_represent：代表元素的终点。
  • find(int[] represent, int x)：寻找顶点x所在集合的代表元素。
    • int[] represent：代表数组代表。
    • int x：待寻找的的顶点。
    • return int x：代表元素的下标。