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