圖解

代碼實現

package com.atguigu.prim;import java.util.Arrays;/*** @創建人 wdl* @創建時間 2021/4/5* @描述*/ public class PrimAlgorithm {public static void main(String[] args) {//測試看看圖是否創建OKchar[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};int verxs = data.length;//鄰接矩陣用二維數組表示,10000這個大數表示這兩個點不連通int [][]weight=new int[][]{{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,10000,10000,5,4},{10000,10000,10000,4,5,10000,6},{2,3,10000,10000,4,6,10000}};//創建MGraph對象MGraph graph = new MGraph(verxs);//創建一個MinTree對象MinTree minTree = new MinTree();minTree.createGraph(graph,verxs,data,weight);//輸出minTree.showGraph(graph);//測試普里姆算法minTree.prim(graph,0);}}//創建最小生成樹->村莊的圖 class MinTree{//創建圖的鄰接矩陣/**** @param graph 圖對象* @param verxs 圖對應的頂點個數* @param data 圖的各個頂點的值* @param weight 圖的鄰接矩陣*/public void createGraph(MGraph graph,int verxs,char data[],int[][] weight){int i,j;for (i = 0; i < verxs; i++) {//頂點graph.data[i]=data[i];for (j = 0; j < verxs; j++) {graph.weight[i][j]=weight[i][j];}}}//顯示圖的鄰接矩陣public void showGraph(MGraph graph){for(int[] link:graph.weight){System.out.println(Arrays.toString(link));}}//編寫一個prim算法，得到最小生成樹/**** @param graph 圖* @param v 表示從圖的第幾個頂點開始生成'A'->0 'B'->1....*/public void prim(MGraph graph,int v){//visited[]標記節點是否被訪問過int[] visited = new int[graph.verxs];//visited[] 默認元素的值都是0，表示沒有訪問過 // for (int i = 0; i < graph.verxs; i++) { // visited[i]=0; // }//把當前這個節點標記為已訪問visited[v]=1;//h1和h2記錄兩個頂點的下標int h1=-1;int h2=-1;int minWeight=10000;//將minWeight初始成一個大數，后面遍歷過程中，會被替換for (int k = 1; k < graph.verxs; k++) {//因為有graph.verxs個頂點，普里姆算法結束后，有graph.verxs-1邊//這個確定每一次生成的子圖，和哪個節點的距離最近for (int i = 0; i < graph.verxs; i++) {//i節點表示被訪問過的節點for (int j = 0; j < graph.verxs; j++) {//j節點表示環沒有訪問過的節點if(visited[i]==1&&visited[j]==0&&graph.weight[i][j]<minWeight){//替換minWeight(尋找已經訪問過的節點和未訪問過的節點間的權值最小的邊)minWeight = graph.weight[i][j];h1=i;h2=j;}}}//找到一條邊是最小System.out.println("邊<"+graph.data[h1]+","+graph.data[h2]+">權值："+minWeight);//將當前這個節點標記為已經訪問visited[h2]=1;//minWeight重新設置為一個最大值10000minWeight=10000;}}}class MGraph{int verxs;//表示圖的節點個數char[] data;//存放結點的數據int [][] weight;//存放邊，就是我們的鄰接矩陣public MGraph(int verxs){this.verxs=verxs;data=new char[verxs];weight=new int[verxs][verxs];}}

總結

以上是生活随笔為你收集整理的普里姆算法(修路问题)+图解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。