1.4.3 最小生成树_自己动手写分布式搜索引擎-QQ阅读男生武侠网

上QQ阅读APP看书，第一时间看更新

1.4.3 最小生成树

在分布式系统中选举主节点时可能会用到最小生成树。一个网络可以用无向连通带权图表示。如图1-9所示为无向连通带权图G。

图1-9 无向连通带权图

遍历图G中所有的顶点的子图G’叫作G的生成树。生成树上各边权的总和称为生成树的耗费。考虑如何用最小的耗费遍历图G中所有的顶点。把得到的子图min(G')叫作G的最小生成树。

用贪心法生成最小生成树的方法是：首先设S = {1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i∈S, j∈V-S且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S = V时为止。这称为Prim算法。

例如，如图1-9所示的图生成最小生成树的过程如下。

得到的最小生成树如图1-10所示。

图1-10 最小生成树

Prim算法求解最小生成树的实现代码如下。

        public class PrimMST {
            public static void main(String[] args) {
                int N = 6; // 节点的数量
                int M = 10; // 边的数量
                HashMap<Integer, HashMap<Integer, Integer>> edgeMap =
                        new HashMap<Integer, HashMap<Integer, Integer>>(); //图


                // 节点编号从1开始
                int[][] graph = { { 1, 6, 2 }, { 1, 1, 3 }, { 1, 5, 4 }, { 2, 5, 3 },
                        { 2, 3, 5 }, { 3, 5, 4 }, { 3, 6, 5 }, { 3, 4, 6 },
                        { 4, 2, 6 }, { 5, 6, 6 } }; //边数组


                for (int i = 0; i < M; i++) {  //生成无向图
                    int n1 = graph[i][0]; // 开始节点
                    int n2 = graph[i][2]; // 结束节点
                    int weight = graph[i][1]; // 权重


                    if (edgeMap.containsKey(n1)) {
                        edgeMap.get(n1).put(n2, weight);
        } else {
            HashMap<Integer, Integer> edge = new HashMap<Integer,
Integer>();
            edge.put(n2, weight);
            edgeMap.put(n1, edge);
        }


        if (edgeMap.containsKey(n2)) {
            edgeMap.get(n2).put(n1, weight);
        } else {
            HashMap<Integer, Integer> edge = new HashMap<Integer,
Integer>();
            edge.put(n1, weight);
            edgeMap.put(n2, edge);
        }
    }


    int S = 1; // 开始节点


    Comparator<CostNode> cmp = new Comparator<CostNode>() {
        public int compare(CostNode node1, CostNode node2) {
            return (node1.cost - node2.cost);
        }
    };


    PriorityQueue<CostNode> costQueue = new PriorityQueue<CostNode>(cmp);
    boolean[] visited = new boolean[N + 1];
    int[] costArray = new int[N + 1];


    for (int i = 1; i <= N; i++) {
        costArray[i] = Integer.MAX_VALUE;
    }


    int numVisited = 0;
    costQueue.add(new CostNode(S, 0));
    costArray[S] = 0;


    while (numVisited < N) {
        CostNode costNode = costQueue.poll();
        int minNode = costNode.node;


        if (! visited[minNode]) {
            visited[minNode] = true;
            numVisited++;


            for (int neighbour : edgeMap.get(minNode).keySet()) {
                if (! visited[neighbour]
                        && edgeMap.get(minNode).get(neighbour) <
        costArray[neighbour]) {
                                costArray[neighbour] = edgeMap.get(minNode).get(
                                        neighbour);


                                costQueue.add(new CostNode(neighbour,
                                        costArray[neighbour]));
                            }
                        }
                    }
                }


                int totalCost = 0;  //生成树的耗费
                for (int i = 1; i <= N; i++) {
                    totalCost += costArray[i];
                }
            }
        }


        class CostNode {
            int node;
            int cost;


            public CostNode(int node, int cost) {
                this.node = node;
                this.cost = cost;
            }
        }