【程序員必會十大算法】之Prim算法

番茄西紅柿發布于2021-09-28 09:36 / 3090人閱讀

摘要：問題勝利鄉有個村莊現在需要修路把個村莊連通各個村莊的距離用邊線表示權比如距離公里問如何修路保證各個村莊都能連通并且總的修建公路總里程最短代碼重點理解中的三層循環

問題

①勝利鄉有7個村莊(A, B,C,D,E,F,G)，現在需要修路把7個村莊連通
②各個村莊的距離用邊線表示(權)，比如A-B距離5公里
③問:如何修路保證各個村莊都能連通，并且總的修建公路總里程最短?

代碼

重點理解createMinTree中的三層for循環

public class Main {    public static void main(String[] args) {        char[] data = {'A','B','C','D','E','F','G'};        int[][] weight = {                {10000,5,7,10000,10000,10000,2},                {5,10000,10000,9,10000, 10000,3},                {7,10000,10000,10000,8,10000,10000},                {10000,9,10000,10000,10000,4,10000},                {10000,10000,8,10006,10000,5,4},                {10000,10000,10000,4,5,10000,6},                {2,3,10000,10000,4,6,10000}};        MGraph mGraph = new MGraph(data.length);        mGraph.createGraph(data,weight);        mGraph.showGraph();        createMinTree(mGraph,0);    }    /**     *     * @param mGraph 表示圖     * @param startIndex 表示開始的點的下標 比如從A開始，則傳0     */    public static void createMinTree(MGraph mGraph,int startIndex){        if (mGraph.vertexNum == 0){            return;        }        //創建是否訪問數組        boolean[] isVisited = new boolean[mGraph.vertexNum];        //全部初始化為 未訪問        for (int i = 0;i < mGraph.vertexNum;i++){            isVisited[i] = false;        }        //將開始的點 設置成 已訪問        isVisited[startIndex] = true;        //創建遍歷到的兩個點的下標        int v1 = -1;        int v2 = -1;        //創建兩點間距離，默認不可達        int v1Tov2 = 10000;        //總共 遍歷mGraph.vertexNum - 1 次，因為是一條邊一條邊遍歷的，生成最小生成樹的時候，邊的數目==點的數目-1        for (int k = 0;k < mGraph.vertexNum - 1;k++){            //每一次都要遍歷 已訪問的節點集合 和 未訪問的節點集合            //但是這個集合我們沒創建出來，所以只能通過遍歷所有的點，通過isVisited進行篩選            for (int i = 0;i < mGraph.vertexNum;i++){                for (int j = 0;j < mGraph.vertexNum;j++){                    //如果有一個點已經訪問，另外一個點沒有被訪問，且兩點間可達或者距離比當前記錄的舉例還要小                    if (isVisited[i] && !isVisited[j] && mGraph.weight[i][j] < v1Tov2){                        //將v1Tov2更新                        v1Tov2 = mGraph.weight[i][j];                        v1 = i;                        v2 = j;                    }                }            }            //遍歷一次，得到兩個點，即一個邊，把這個邊記錄下來            System.out.println("邊<"+ mGraph.data[v1] + "," + mGraph.data[v2]+"> 權值:"+ v1Tov2);            //然后為下一次遍歷做初始化操作            isVisited[v2] = true;            v1Tov2 = 10000;        }    }}//這是圖class MGraph{    //節點數目    int vertexNum;    //節點    char[] data;    //邊的權值    int[][] weight;    MGraph(int vertexNum){        this.vertexNum = vertexNum;        data = new char[vertexNum];        weight = new int[vertexNum][vertexNum];    }    //圖的創建    public void createGraph(char[] mData,int[][] mWeight){        if (vertexNum == 0){            return;//節點數目為0 無法創建        }        for (int i = 0;i < data.length;i++){            data[i] = mData[i];        }        for (int i = 0;i < mWeight.length;i++){            for (int j = 0;j < mWeight.length;j++){                weight[i][j] = mWeight[i][j];            }        }    }    //打印圖    public void showGraph(){        if (vertexNum == 0){            return;        }        for (int[] oneLine: weight){            for (int oneNum: oneLine){                System.out.print(oneNum + " ");            }            System.out.println();        }    }}

結果

邊<A,G> 權值:2邊<G,B> 權值:3邊<G,E> 權值:4邊<E,F> 權值:5邊<F,D> 權值:4邊<A,C> 權值:7

云服務器 GPU云服務器最小生成樹prim算法實驗報告 webrtc之vad算法十大機器學習算法機器學習十大算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/121402.html

【程序員必會十大算法】之分治算法（漢諾塔問題）

摘要：應用分治法是一種很重要的算法。字面上的解釋是分而治之，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。 ...

codecraft 2021-09-24 09:48 評論0 收藏0
【程序員必會十大算法】之二分查找算法

摘要：遞歸實現不考慮相同數二分查找，不考慮有相同數的情況遞歸找到了考慮有相同數二分查找考慮有相同元素的情況遞歸要查找的值 1.遞歸實現 ①不考慮相同數 /** * 二分查...

YFan 2021-09-24 09:48 評論0 收藏0
【程序員必會十大算法】之弗洛伊德算法

摘要：學習資料迪杰斯特拉計算的是單源最短路徑，而弗洛伊德計算的是多源最短路徑代碼不能設置為，否則兩個相加會溢出導致出現負權創建頂點和邊學習資料迪杰斯特拉計算的是單源最...

JellyBool 2021-09-30 09:47 評論0 收藏0
【程序員必會十大算法】之貪心算法

摘要：例題假設存在如下表的需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區。例題假設存在如下表的需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區。如何選擇最少的廣播臺，讓...

macg0406 2021-09-27 13:36 評論0 收藏0
【程序員必會十大算法】之騎士周游問題

摘要：騎士周游問題又叫馬踏棋盤問題未優化前沒有策略定義棋盤的行數和列數定義棋盤上的某個點是否被訪問過記錄是否周游結束從第一行第一列開始走，第一次走算第一步，即展示下是棋盤， ...

Baoyuan 2021-09-30 09:47 評論0 收藏0