快捷導(dǎo)航

Java圖論進(jìn)階之最小生成樹(shù)算法詳解

更新時(shí)間：2023年01月10日 12:38:23 作者：Node_Hao

最小生成樹(shù)（Minimum Spanning Tree）就是給定無(wú)向圖中,邊權(quán)重最小的生成樹(shù),下面這篇文章主要給大家介紹了關(guān)于Java圖論進(jìn)階之最小生成樹(shù)算法的相關(guān)資料,文中通過(guò)圖文以及實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下

1. 最小生成樹(shù)

連通圖中的每一棵生成樹(shù) , 都是原圖的極大無(wú)環(huán)子圖 , 即: 從中刪去任何一條邊 , 生成樹(shù)就不再連通;反之 , 在其中引入任何一條新邊 , 都會(huì)形成一條回路.

若連通圖由n個(gè)頂點(diǎn)組成 , 則其生成樹(shù)必含n個(gè)頂點(diǎn)和n-1條邊 , 因此構(gòu)造最小生成樹(shù)有三個(gè)準(zhǔn)則:

1.只能使用圖中的邊來(lái)構(gòu)造最小生成樹(shù)
2.只能使用恰好n-1條邊來(lái)連接圖中的n個(gè)頂點(diǎn)
3.選用的n-1條邊不能構(gòu)成回路

常見(jiàn)求解最小生成樹(shù)的算法有: Kruskal算法和Prime算法.兩種算法都采用逐步求解的貪心策略.

貪心算法: 通過(guò)局部最優(yōu)解來(lái)推出全局最優(yōu)解.

1.1 Kruskal(克魯斯卡爾) 算法

給定一個(gè)有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)N={V,E}

首先構(gòu)造一個(gè)由這n個(gè)頂點(diǎn)組成 , 不含任何邊的圖G={V,NULL}.

其次不斷從E中取出權(quán)值最小的一條邊(若有多條任選其一) , 若該邊的兩個(gè)頂點(diǎn)來(lái)自不同的連通分量 , 則將此邊加入到G中.

如此反復(fù) , 直到G中邊數(shù)達(dá)到頂點(diǎn)數(shù)-1為止.

核心: 每次迭代時(shí) , 選出權(quán)值最小且兩端點(diǎn)不在同一連通分量上的邊 , 加入生成樹(shù).

步驟分析:

1.由于該算法的思想是全局貪心 , 因此將所有圖中所有邊全部放入優(yōu)先級(jí)隊(duì)列中.
2.構(gòu)造一個(gè)最小生成樹(shù) , 將優(yōu)先級(jí)隊(duì)列中的邊依次加入.
3.為了防止出現(xiàn)環(huán) , 使用并查集判斷每次取出的邊的頂點(diǎn)是否來(lái)自同一個(gè)集合 .
4.如果不是同一集合 , 將該邊加入最小生成樹(shù)并用并查集將該邊的領(lǐng)接頂點(diǎn)放入同一個(gè) 集合.

代碼示例:

 /**
     * 克魯斯卡爾算法實(shí)現(xiàn)
     * @param minTree
     * @return
     */
    /**
     * 模擬實(shí)現(xiàn)一條邊
     */
    static class Edge{
        public int srcIndex;
        public int destIndex;
        public int weight;
 
        public Edge(int srcIndex, int destIndex, int weight) {
            this.srcIndex = srcIndex;
            this.destIndex = destIndex;
            this.weight = weight;
        }
    }
 
    public int kruskal(GraphOfMatrix minTree) {
        //1.定義一個(gè)優(yōu)先級(jí)隊(duì)列
        PriorityQueue<Edge> minQ = new PriorityQueue<Edge>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        int n = arrayV.length;
        //2.遍歷領(lǐng)接矩陣,將所有的邊都放入優(yōu)先級(jí)隊(duì)列中
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i < j && Matrix[i][j] != Integer.MIN_VALUE) {
                    minQ.offer(new Edge(i, j, Matrix[i][j]));
                }
            }
        }
        //3.構(gòu)造并查集將符合要求的邊加入到最小生成樹(shù)中
        UnionFindSet ufs = new UnionFindSet(n);
 
        int size = 0;//記錄最小生成樹(shù)中邊的數(shù)量
        int totalWeight = 0;//記錄權(quán)值
        while (size < n - 1 && !minQ.isEmpty()) {
            Edge edge = minQ.poll();
            int srcIndex = edge.srcIndex;
            int destIndex = edge.destIndex;
            //同一邊的相鄰頂點(diǎn)不能來(lái)自同一集合
            if (!ufs.isSameUnionFindSet(srcIndex, destIndex)) {
                //將符合條件的邊加入到最小生成樹(shù)中
                minTree.addEdgeUseIndex(srcIndex, destIndex, Matrix[srcIndex][destIndex]);
                System.out.println("選擇的邊"+arrayV[srcIndex]+" -> "+arrayV[destIndex]+Matrix[srcIndex][destIndex]);
                size++;
                totalWeight += Matrix[srcIndex][destIndex];
                //將添加過(guò)的邊的相鄰頂點(diǎn)放入同一集合,防止出現(xiàn)環(huán).
                ufs.union(srcIndex, destIndex);
            }
        }
        if (size == n - 1) {
            return totalWeight;
        } else {
            throw new RuntimeException("沒(méi)有最小生成樹(shù)");
        }
    }
 
   //按照下標(biāo)將邊加入到最小生成樹(shù)中
    public void addEdgeUseIndex(int srcIndex,int destIndex,int weight){
        Matrix[srcIndex][destIndex] = weight;
        //如果是無(wú)向圖鄰接矩陣對(duì)稱(chēng)位置也要添加
        if (!isDirect){
            Matrix[destIndex][srcIndex] = weight;
        }
    }
    //測(cè)試克魯斯卡爾算法
    public static void main(String[] args) {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        graph.GraphOfMatrix g = new graph.GraphOfMatrix(str.length(),false);
        g.initArray(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        graph.GraphOfMatrix kminTree = new graph.GraphOfMatrix(str.length(),false);
        System.out.println(g.kruskal(kminTree));
        kminTree.printGraph();
    }

構(gòu)造并查集:

public class UnionFindSet {
    public int[] elem;
 
    public UnionFindSet(int n){
        this.elem = new int[n];
        Arrays.fill(elem,-1);
    }
 
    /**
     * 查找數(shù)據(jù)x的根節(jié)點(diǎn)
     * @param x
     * @return
     */
    public int findRoot(int x){
        if (x < 0){
            throw new RuntimeException("下表不合法");
        }
        while (elem[x] >= 0){
            x = elem[x];
        }
        return x;
    }
    /**
     * 查詢(xún)x1和x2是不是同一個(gè)集合
     * @param x1
     * @param x2
     * @return
     */
    public boolean isSameUnionFindSet(int x1 , int x2){
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if (index1 == index2){
            return true;
        }
        return false;
    }
 
    /**
     * 這是合并操作
     * @param x1
     * @param x2
     */
    public void union(int x1 , int x2){
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if (index1 == index2) return;
        elem[index1] = elem[index1] + elem[index2];
        elem[index2] = index1;
    }
 
    /**
     * 有幾對(duì)關(guān)系
     * @return
     */
    public int getCount(){
        int count = 0;
        for (int x:elem) {
            if (x < 0){
                count++;
            }
        }
        return count;
    }
    public void Print(){
        for (int x:elem){
            System.out.print(x+" ");
        }
        System.out.println();
    }
}

測(cè)試結(jié)果:

1.2 Prime(普里姆) 算法

普里姆算法與克魯斯卡爾算法類(lèi)似 , 核心區(qū)別是普里姆算法采用局部貪心的思想.

首先 , 設(shè)定兩個(gè)集合 , X{}已確定頂點(diǎn)的集合 , Y{}未確定頂點(diǎn)的集合.

其次 , 假設(shè)圖中的頂點(diǎn)為 a,b,c,d,e,f,g,h,i.放入Y{}中.

然后 , 任取一個(gè)頂點(diǎn)放入X{}中 . 在Y{}中選擇一個(gè)與該頂點(diǎn)相連權(quán)值最小的邊 , 加入最小生成樹(shù)中.

如此重復(fù) , 直到最小生成樹(shù)的邊數(shù)達(dá)到頂點(diǎn)數(shù)-1為止.

代碼示例:

/**
     * 普里姆算法實(shí)現(xiàn)
     * @param minTree
     * @param chV 圖中頂點(diǎn)的起點(diǎn)
     * @return
     */
    public int prime(GraphOfMatrix minTree,char chV) {
        int srcIndex = getIndexOfV(chV);
        //存儲(chǔ)已確定的頂點(diǎn)
        Set<Integer> setX = new HashSet<>();
        setX.add(srcIndex);
        //初始化未確定的點(diǎn)
        Set<Integer> setY = new HashSet<>();
        int n = arrayV.length;
        for (int i = 0; i < n; i++) {
            if (i != srcIndex){
                setY.add(i);
            }
        }
        //定義一個(gè)優(yōu)先級(jí)隊(duì)列
        PriorityQueue<Edge> minQ = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        //遍歷srcIndex連接出去的邊,并放入優(yōu)先級(jí)隊(duì)列中排序
        for (int i = 0; i < n; i++) {
            if (Matrix[srcIndex][i] != Integer.MIN_VALUE){
                minQ.offer(new Edge(srcIndex,i,Matrix[srcIndex][i]));
            }
        }
        int size = 0;
        int totalWeight = 0;
        while (!minQ.isEmpty()){
            Edge min = minQ.poll();
            int srcI = min.srcIndex;
            int destI = min.destIndex;
            if (setX.contains(destI)){
                //此時(shí)會(huì)構(gòu)成環(huán)
            }else {
                minTree.addEdgeUseIndex(srcI,destI,Matrix[srcI][destI]);
                System.out.println("起點(diǎn)"+arrayV[srcI]+" -> "+"終點(diǎn)"+arrayV[destI]+Matrix[srcI][destI]);
                size++;
                totalWeight+=min.weight;
                if (size == n-1){
                    return totalWeight;
                }
                //更新兩個(gè)集合
                setX.add(destI);
                setY.remove(destI);
                //把dest連出去的所有邊也放到優(yōu)先級(jí)隊(duì)列中
                for (int i = 0; i < n; i++) {
                    if (Matrix[destI][i] != Integer.MIN_VALUE && !setX.contains(i)){
                        minQ.offer(new Edge(destI,i,Matrix[destI][i]));
                    }
                }
            }
        }
       throw new RuntimeException("沒(méi)有最小生成樹(shù)");
    }
    //測(cè)試普里姆算法
    public static void main3(String[] args) {
            String str = "abcdefghi";
            char[] array =str.toCharArray();
            GraphOfMatrix g = new GraphOfMatrix(str.length(),false);
            g.initArray(array);
            g.addEdge('a', 'b', 4);
            g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
            g.addEdge('b', 'c', 8);
            g.addEdge('b', 'h', 11);
            g.addEdge('c', 'i', 2);
            g.addEdge('c', 'f', 4);
            g.addEdge('c', 'd', 7);
            g.addEdge('d', 'f', 14);
            g.addEdge('d', 'e', 9);
            g.addEdge('e', 'f', 10);
            g.addEdge('f', 'g', 2);
            g.addEdge('g', 'h', 1);
            g.addEdge('g', 'i', 6);
            g.addEdge('h', 'i', 7);
            GraphOfMatrix primTree = new GraphOfMatrix(str.length(),false);
            System.out.println(g.prime(primTree,'a'));
            primTree.printGraph();
    }