mg电子不朽情缘手法技巧

書名：自己動(dòng)手寫分布式搜索引擎
作者名：羅剛
本章字?jǐn)?shù)： 677字
更新時(shí)間： 2020-11-28 15:52:40

1.4.3 最小生成樹

在分布式系統(tǒng)中選舉主節(jié)點(diǎn)時(shí)可能會(huì)用到最小生成樹。一個(gè)網(wǎng)絡(luò)可以用無向連通帶權(quán)圖表示。如圖1-9所示為無向連通帶權(quán)圖G。

圖1-9 無向連通帶權(quán)圖

遍歷圖G中所有的頂點(diǎn)的子圖G’叫作G的生成樹。生成樹上各邊權(quán)的總和稱為生成樹的耗費(fèi)?？紤]如何用最小的耗費(fèi)遍歷圖G中所有的頂點(diǎn)。把得到的子圖min(G')叫作G的最小生成樹。

用貪心法生成最小生成樹的方法是：首先設(shè)S = {1}，然后，只要S是V的真子集，就進(jìn)行如下的貪心選擇：選取滿足條件i∈S, j∈V-S且c[i][j]最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過程一直進(jìn)行到S = V時(shí)為止。這稱為Prim算法。

例如，如圖1-9所示的圖生成最小生成樹的過程如下。

得到的最小生成樹如圖1-10所示。

圖1-10 最小生成樹

Prim算法求解最小生成樹的實(shí)現(xiàn)代碼如下。

        public class PrimMST {
            public static void main(String[] args) {
                int N = 6; // 節(jié)點(diǎn)的數(shù)量
                int M = 10; // 邊的數(shù)量
                HashMap<Integer, HashMap<Integer, Integer>> edgeMap =
                        new HashMap<Integer, HashMap<Integer, Integer>>(); //圖


                // 節(jié)點(diǎn)編號(hào)從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 } }; //邊數(shù)組


                for (int i = 0; i < M; i++) {  //生成無向圖
                    int n1 = graph[i][0]; // 開始節(jié)點(diǎn)
                    int n2 = graph[i][2]; // 結(jié)束節(jié)點(diǎn)
                    int weight = graph[i][1]; // 權(quán)重


                    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; // 開始節(jié)點(diǎn)


    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;  //生成樹的耗費(fèi)
                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;
            }
        }

官术网_书友最值得收藏!

自己動(dòng)手寫分布式搜索引擎

1.4.3 最小生成樹