一 背景

二 ?prim算法java版

package leaning.graph;/** 最小生成樹之普里姆算法* */ public class PrimMiniCostSpanningTree {//總權值private int totalCounter = 0 ; //總權值StringBufferprivate StringBuffer stringBuffer = new StringBuffer();//計數器private int counter =0;//最大Int整數,表示無窮大private int MAX_VALUE = Integer.MAX_VALUE;//定義地圖變量private int map[][] = new int[9][9]; //定義節點private String nodes[] = {"vo","v1","v2","v3","v4","v5","v6","v7","v8"};//保存相關頂點邊的權值private int lowCost[] = new int[9];//保存相關頂點下標private int adjvex[] = new int[9];public PrimMiniCostSpanningTree(){this.init();}//初始化地圖public void initMap(){this.map[0] = new int[]{ 0, 10,MAX_VALUE,MAX_VALUE,MAX_VALUE, 11,MAX_VALUE,MAX_VALUE,MAX_VALUE};this.map[1] = new int[]{ 10, 0, 18,MAX_VALUE,MAX_VALUE,MAX_VALUE, 16,MAX_VALUE, 12};this.map[2] = new int[]{MAX_VALUE,MAX_VALUE, 0, 22,MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE, 8};this.map[3] = new int[]{MAX_VALUE,MAX_VALUE, 22, 0, 20,MAX_VALUE,MAX_VALUE, 16, 21};this.map[4] = new int[]{MAX_VALUE,MAX_VALUE,MAX_VALUE, 20, 0, 26,MAX_VALUE, 7,MAX_VALUE};this.map[5] = new int[]{ 11,MAX_VALUE,MAX_VALUE,MAX_VALUE, 26, 0, 17,MAX_VALUE,MAX_VALUE};this.map[6] = new int[]{MAX_VALUE, 16,MAX_VALUE,MAX_VALUE,MAX_VALUE, 17, 0, 19,MAX_VALUE};this.map[7] = new int[]{MAX_VALUE,MAX_VALUE,MAX_VALUE, 16, 7,MAX_VALUE, 19, 0,MAX_VALUE};this.map[8] = new int[]{MAX_VALUE, 12, 8, 21,MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE, 0};}//初始化參數public void init(){//1 初始化地圖this.initMap();//2 初始化lowCost和adjvexfor(int i = 0 ; i < this.lowCost.length ;i++){this.lowCost[i] = 0;this.adjvex[i] = 0;}}// 普里姆算法核心public void prim(){// 1 取 v0 頂點,并為lowCost賦值for(int i = 0 ; i < this.lowCost.length ;i++){this.lowCost[i] = this.map[0][i];}for(int j = 1 ; j < this.lowCost.length ;j++){// 2 從lowcost中計算得到最小權值int min = MAX_VALUE;int position = -1; //記錄最小權值的位置for(int i = 0 ; i < this.lowCost.length ;i++){if( this.lowCost[i]!=0 && min > this.lowCost[i] ){min = this.lowCost[i];position = i;}}// 3 得到最小值，并輸出this.counter++;System.out.println("第 "+this.counter+" 條邊為 : ["+this.nodes[this.adjvex[position]]+","+this.nodes[position]+"] = "+this.lowCost[position]+" ");totalCounter = totalCounter + this.lowCost[position];this.stringBuffer.append(this.lowCost[position]+"+");// 4 調整adjvex和lowCost的值this.lowCost[position] = 0;this.adjvex[position] = 0;for(int i = 0 ; i < this.lowCost.length ;i++){if(this.map[position][i]!=0 && this.map[position][i]!=this.MAX_VALUE && this.lowCost[i]!=0 && this.lowCost[i] > this.map[position][i] ){this.lowCost[i] = this.map[position][i];this.adjvex[i] = position;}}}String result = this.stringBuffer.toString();result = result.substring(0,result.length()-1);System.out.println("總權值為 : " + result + " = " + this.totalCounter );}public static void main(String[] args) {PrimMiniCostSpanningTree primMiniCostSpanningTree = new PrimMiniCostSpanningTree();primMiniCostSpanningTree.prim();}}
三 運行結果圖

總結

以上是生活随笔為你收集整理的最小生成树之prim算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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