資訊專欄INFORMATION COLUMN
摘要：問題勝利鄉(xiāng)有個村莊現(xiàn)在需要修路把個村莊連通各個村莊的距離用邊線表示權(quán)比如距離公里問如何修路保證各個村莊都能連通并且總的修建公路總里程最短代碼重點理解中的三層循環(huán)
①勝利鄉(xiāng)有7個村莊(A, B,C,D,E,F,G)，現(xiàn)在需要修路把7個村莊連通
②各個村莊的距離用邊線表示(權(quán))，比如A-B距離5公里
③問:如何修路保證各個村莊都能連通，并且總的修建公路總里程最短?
重點理解createMinTree中的三層for循環(huán)
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 表示開始的點的下標(biāo) 比如從A開始，則傳0 */ public static void createMinTree(MGraph mGraph,int startIndex){ if (mGraph.vertexNum == 0){ return; } //創(chuàng)建是否訪問數(shù)組 boolean[] isVisited = new boolean[mGraph.vertexNum]; //全部初始化為 未訪問 for (int i = 0;i < mGraph.vertexNum;i++){ isVisited[i] = false; } //將開始的點 設(shè)置成 已訪問 isVisited[startIndex] = true; //創(chuàng)建遍歷到的兩個點的下標(biāo) int v1 = -1; int v2 = -1; //創(chuàng)建兩點間距離，默認(rèn)不可達(dá) int v1Tov2 = 10000; //總共 遍歷mGraph.vertexNum - 1 次，因為是一條邊一條邊遍歷的，生成最小生成樹的時候，邊的數(shù)目==點的數(shù)目-1 for (int k = 0;k < mGraph.vertexNum - 1;k++){ //每一次都要遍歷 已訪問的節(jié)點集合 和 未訪問的節(jié)點集合 //但是這個集合我們沒創(chuàng)建出來，所以只能通過遍歷所有的點，通過isVisited進(jìn)行篩選 for (int i = 0;i < mGraph.vertexNum;i++){ for (int j = 0;j < mGraph.vertexNum;j++){ //如果有一個點已經(jīng)訪問，另外一個點沒有被訪問，且兩點間可達(dá)或者距離比當(dāng)前記錄的舉例還要小 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]+"> 權(quán)值:"+ v1Tov2); //然后為下一次遍歷做初始化操作 isVisited[v2] = true; v1Tov2 = 10000; } }}//這是圖class MGraph{ //節(jié)點數(shù)目 int vertexNum; //節(jié)點 char[] data; //邊的權(quán)值 int[][] weight; MGraph(int vertexNum){ this.vertexNum = vertexNum; data = new char[vertexNum]; weight = new int[vertexNum][vertexNum]; } //圖的創(chuàng)建 public void createGraph(char[] mData,int[][] mWeight){ if (vertexNum == 0){ return;//節(jié)點數(shù)目為0 無法創(chuàng)建 } 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(); } }}結(jié)果
邊<A,G> 權(quán)值:2邊<G,B> 權(quán)值:3邊<G,E> 權(quán)值:4邊<E,F> 權(quán)值:5邊<F,D> 權(quán)值:4邊<A,C> 權(quán)值:7文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/121402.html
摘要：應(yīng)用分治法是一種很重要的算法。字面上的解釋是分而治之，就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。 ...
摘要：遞歸實現(xiàn)不考慮相同數(shù)二分查找，不考慮有相同數(shù)的情況遞歸找到了考慮有相同數(shù)二分查找考慮有相同元素的情況遞歸要查找的值 1.遞歸實現(xiàn) ①不考慮相同數(shù) /** * 二分查...
摘要：學(xué)習(xí)資料迪杰斯特拉計算的是單源最短路徑，而弗洛伊德計算的是多源最短路徑代碼不能設(shè)置為，否則兩個相加會溢出導(dǎo)致出現(xiàn)負(fù)權(quán)創(chuàng)建頂點和邊 學(xué)習(xí)資料 迪杰斯特拉計算的是單源最...
摘要：例題假設(shè)存在如下表的需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區(qū)。 例題 假設(shè)存在如下表的需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區(qū)。如何選擇最少的廣播臺，讓...
摘要：騎士周游問題又叫馬踏棋盤問題未優(yōu)化前沒有策略定義棋盤的行數(shù)和列數(shù)定義棋盤上的某個點是否被訪問過記錄是否周游結(jié)束從第一行第一列開始走，第一次走算第一步，即展示下是棋盤， ...
閱讀 847·2023-04-25 19:43
閱讀 4115·2021-11-30 14:52
閱讀 3930·2021-11-30 14:52
閱讀 4027·2021-11-29 11:00
閱讀 3921·2021-11-29 11:00
閱讀 4039·2021-11-29 11:00
閱讀 3769·2021-11-29 11:00
閱讀 6607·2021-11-29 11:00
