日擼代碼300行（31-40天，圖）

原文：日擼代碼300行（31-40天，圖）_minfanphd的博客-CSDN博客

31.整數(shù)矩陣及其運算

package day40;import day10.MatrixMultiplication;import java.util.Arrays;/*** Day 31 整數(shù)矩陣** @author pzf*/
public class IntMatrix {// 變量int[][] data; // 二維數(shù)組/*** 構造方法1** @param paraRows    行* @param paraColumns 列*/public IntMatrix(int paraRows, int paraColumns) {this.data = new int[paraRows][paraColumns];}// Of the first contractor/*** 構造方法2 復制數(shù)組** @param paraMatrix 二維矩陣*/public IntMatrix(int[][] paraMatrix) {this.data = new int[paraMatrix.length][paraMatrix[0].length];for (int i = 0; i < paraMatrix.length; i++) {for (int j = 0; j < paraMatrix[0].length; j++) {data[i][j] = paraMatrix[i][j];}// Of for j}// Of for i}// Of the second contractorpublic IntMatrix(IntMatrix paraMatrix) {this.data = paraMatrix.getData();}// Of the third contractor/*** 獲取單位矩陣** @param paraRows 單位矩陣的行列數(shù)* @return 單位矩陣*/public static IntMatrix getIdentityMatrix(int paraRows) {IntMatrix resMatrix = new IntMatrix(paraRows, paraRows);for (int i = 0; i < paraRows; i++) {resMatrix.data[i][i] = 1;}// Of forreturn resMatrix;}// Of getIdentityMatrix/*** 重寫toString** @return 字符串*/public String toString() {return Arrays.deepToString(data);}// Of toString/*** Getter* @return data*/public int[][] getData() {return data;}/*** setter 在指定行列賦指定值** @param paraRow 行* @param paraCol 列* @param paraValue 值*/public void setValue(int paraRow,int paraCol,int paraValue){this.data[paraRow][paraCol] = paraValue;}/*** getter 獲取指定位置的值** @param paraRow 行* @param paraCol 列* @return 值*/public int getValue(int paraRow,int paraCol){return this.data[paraRow][paraCol];}/*** 矩陣相加** @param paraMatrix 要加上的矩陣* @throws Exception 矩陣的行或列不匹配*/public void addMatrix(IntMatrix paraMatrix) throws Exception {int[][] tempMatrix = this.getData();if (tempMatrix.length!=paraMatrix.data.length || tempMatrix[0].length!=paraMatrix.data[0].length){throw new Exception("Cannot add matrices.");}// Of iffor (int i = 0; i < tempMatrix.length; i++) {for (int j = 0; j < tempMatrix[0].length; j++) {this.data[i][j] += paraMatrix.data[i][j];}// Of for j}// Of for i}// Of addMatrix/*** 矩陣相加** @param paraMatrix1 矩陣1* @param paraMatrix2 矩陣2* @return 新矩陣* @throws Exception 矩陣的行或列不匹配*/public IntMatrix addMatrix(IntMatrix paraMatrix1,IntMatrix paraMatrix2) throws Exception {IntMatrix resMatrix = new IntMatrix(paraMatrix1);resMatrix.addMatrix(paraMatrix2);return resMatrix;}// Of addMatrix/*** 矩陣相乘** @param paraMatrix1 矩陣1* @param paraMatrix2 矩陣2* @return 新矩陣* @throws Exception 矩陣的行或列不匹配*/public static IntMatrix multiplyMatrix(IntMatrix paraMatrix1,IntMatrix paraMatrix2) throws Exception {// Day8的方法 int[][] multiplication(int[][] paraMatrix1, int[][] paraMatrix2)int[][] tempArray = MatrixMultiplication.multiplication(paraMatrix1.getData(),paraMatrix2.getData());if (tempArray==null){throw new Exception("Cannot multiply matrices.");}// Of ifreturn new IntMatrix(tempArray);}// Of multipleMatrix/*** 判斷是否為無向圖(鄰接矩陣對稱)** @return 是: true, 否: false.*/public boolean isUndirected(){int numNodes = this.getRows();int[][] tempMatrix = this.getData();for (int i = 1; i < numNodes; i++) {for (int j = 0; j < i; j++) {if (tempMatrix[i][j] != tempMatrix[j][i]){return false;}// Of if}// Of for j}// Of for ireturn true;}// Of isUndirectedpublic static void main(String[] args) {int[][] test = {{1, 2, 3}, {1, 2, 3}, {1, 2, 3}};int[][] test2 = {{1, 2}, {1, 2}, {1, 2}, {1, 2}};IntMatrix i = new IntMatrix(test);IntMatrix j1 = new IntMatrix(test);IntMatrix j2 = new IntMatrix(test2);try {System.out.println(multiplyMatrix(i,j1).toString());System.out.println(multiplyMatrix(j1,j2).toString());} catch (Exception e) {e.printStackTrace();}// Of try}// Of main}// Of class IntMatrix

32.圖的連通性檢測

相關補習：

32.1 如何判斷連通性？

定義1：設有向圖 D = ? V , E ? , V = { v 1 , v 2 , . . . , v n } , D=\langle V,E\rangle,V=\{v_1,v_2,...,v_n\}, D=?V,E?,V={v1?,v2?,...,vn?},令$a_{ij}^{(1)}$為頂點$v_i$到頂點$v_j$的邊數(shù)，稱$(a_{ij}^{(1)}{)}_{m\times n}$為$D$的鄰接矩陣，記作$A(D)$，簡記為$A$.

定理1：$A$的$l$次冪$A^l$中元素$a_{ij}^{(l)}$為$D$中$v_i$到$v_j$長度為$l$的通路數(shù)。

證明：$l=1$時，根據(jù)鄰接矩陣定義，$a_{ij}^{(1)}$等于$v_i$到$v_j$長度為1的通路數(shù)，結論成立。
假設對$l$成立，即$a_{ij}^{(l)}$等于$v_i$到$v_j$長度為$l$的通路數(shù)，要證結論對$l+1$成立。
因為$v_i$到$v_j$長度為$l+1$的一條通路由$v_i$到某一點$v_k$的通路加$v_k$到$v_j$的一條邊組成，根據(jù)歸納假設，$v_i$到$v_k$長度為$l$的通路數(shù)等于$a_{ik}^{(l)}$，所以$v_i$到$v_j$長度為$l+1$的通路數(shù)等于
$$\sum _{k=1}^n{a}_{ik}^{(l)}?a_{kj}^{(1)}=a_{ij}^{(l+1)}$$
得證對$l+1$結論成立。

推論：設$B_l=A+A^2+...+A^l(l\ge 1)$，$B_l$中元素之和$\sum _{i=1}^n\sum _{j=1}^n{b}_{ij}^{(l)}$為$D$中長度小于等于$l$的通路數(shù)。

定義2：有向圖 D = ? V , E ? , V = { v 1 , v 2 , . . . , v n } D=\langle V,E\rangle,V=\{v_1,v_2,...,v_n\} D=?V,E?,V={v1?,v2?,...,vn?}令$$p_{ij}=\{\begin{array}{rlr}1,& & v_i可達v_j\\ 0,& & 否則\end{array}$$
稱$(p_{ij}{)}_{m\times n}$為$D$的可達矩陣，記作$P(D)$，簡記為$P$.

定理2：在$n$階圖$G$中，若從頂點$u$到$v$$(u=v)$存在通路，則從$u$到$v$存在長度小于等于$n?1$的通路。

由定理2和定理1的推論可知，只要計算出$B_{n?1}$，由$B_{n?1}$的元素$b_{ij}^{(n?1)}$是否為0就可以寫出$D$的可達矩陣。不過$p_{ii}$總為1，與$B_{n?1}$

參考自《離散數(shù)學》

package day40;/*** Day 32:有向圖，無向圖作為其中一種特殊情況** @author pzf*/
public class Graph {IntMatrix connectivityMatrix;/*** 構造方法** @param paraNumNodes 頂點數(shù)*/public Graph(int paraNumNodes) {this.connectivityMatrix = new IntMatrix(paraNumNodes,paraNumNodes);}// Of contractor/*** 構造方法** @param paraMatrix 鄰接矩陣*/public Graph(int[][] paraMatrix){this.connectivityMatrix = new IntMatrix(paraMatrix);}// Of contractor/*** 重寫toString** @return 字符串*/public String toString() {String resultString = "This is the connectivity matrix of the graph.\r\n"+ connectivityMatrix;return resultString;}// Of toString/*** 得到連通矩陣** @return True or false* @throws Exception 不是方陣*/public boolean getConnectivity() throws Exception {// 1.單位矩陣IntMatrix tempConnectivityMatrix = IntMatrix.getIdentityMatrix(connectivityMatrix.getData().length);// 2.可達矩陣 或 鄰接矩陣IntMatrix temMultipliedMatrix = new IntMatrix(connectivityMatrix);// 3.確定M_afor (int i = 0; i < connectivityMatrix.getData().length-1; i++) {// M_a = M_a + M^ktempConnectivityMatrix.addMatrix(temMultipliedMatrix);// 指數(shù)+1temMultipliedMatrix = IntMatrix.multiplyMatrix(temMultipliedMatrix,connectivityMatrix);}// Of for// 4.判斷聯(lián)通System.out.println("The connectivity matrix is: " + tempConnectivityMatrix);int[][] tempData = tempConnectivityMatrix.getData();for (int i = 0; i < tempData.length; i++) {for (int j = 0; j < tempData.length; j++) {if(tempData[i][j]==0){System.out.println("Node " + i + " cannot reach " + j);return false;}// Of if}// Of for j}// Of for ireturn true;}// Of getConnectivity/*** 單元測試*/public static void getConnectivityTest() {// Test an undirected graph.int[][] tempMatrix = { { 0, 1, 0 }, { 1, 0, 1 }, { 0, 1, 0 } };Graph tempGraph2 = new Graph(tempMatrix);System.out.println(tempGraph2);boolean tempConnected = false;try {tempConnected = tempGraph2.getConnectivity();} catch (Exception ee) {System.out.println(ee);} // Of try.System.out.println("Is the graph connected? " + tempConnected);}// Of getConnectivityTest/*** main** @param args*/public static void main(String args[]) {getConnectivityTest();}// Of main}// Of class Graph

33.圖的廣度優(yōu)先遍歷

    /*** 廣度遍歷** @param paraStartIndex 起始點* @return 遍歷字符串*/public String breadthFirstTraversal(int paraStartIndex) {// 初始化隊列、字符串AnyQueue tempQueue = new AnyQueue();String resString = "";// 獲取節(jié)點數(shù)int tempNodesNum = connectivityMatrix.getRows();// 標記已訪問過的boolean[] tempVisitedArray = new boolean[tempNodesNum];tempVisitedArray[paraStartIndex] = true;resString += paraStartIndex;// 起始頂點進隊//tempQueue.enqueue(paraStartIndex);//int tempIndex;Integer tempInteger = paraStartIndex;while (tempInteger != null) {// 矩陣對應行//tempIndex = tempInteger;// 遍歷節(jié)點for (int i = 0; i < tempNodesNum; i++) {// 訪問過 跳過if (tempVisitedArray[i]) {continue;}// Of if// 無通路 跳過if (connectivityMatrix.getData()[tempInteger][i] == 0) {continue;}// Of if// 標記 已訪問tempVisitedArray[i] = true;// 拼接該節(jié)點resString += i;// 入隊tempQueue.enqueue(i);}// Of for// 出隊 訪問剩余節(jié)點時用tempInteger = (Integer) tempQueue.dequeue();}// Of whilereturn resString;}//Of breadthFirstTraversal/*** 廣度遍歷單元測試*/public static void breadthFirstTraversalTest() {// Test an undirected graph.int[][] tempMatrix = {{0, 1, 1, 0, 1}, {1, 0, 0, 1, 1}, {1, 0, 0, 0, 1}, {0, 0, 1, 0, 0}, {1, 0, 1, 0, 1}};Graph tempGraph = new Graph(tempMatrix);System.out.println(tempGraph);String tempSequence = "";try {tempSequence = tempGraph.breadthFirstTraversal(2);} catch (Exception ee) {System.out.println(ee);} // Of try.System.out.println("The breadth first order of visit: " + tempSequence);}//Of breadthFirstTraversalTest

結果：

[[0, 1, 1, 0, 1], [1, 0, 0, 1, 1], [1, 0, 0, 0, 1], [0, 0, 1, 0, 0], [1, 0, 1, 0, 1]]
The breadth first order of visit: 20413

做了一些修改，省略了一開始的入隊出隊；感覺不需要tempInteger和tempIndex兩個變量，精簡成一個了，Java還是會自動轉(zhuǎn)換Integer和int.

34.圖的深度優(yōu)先遍歷

/*** 深度優(yōu)先遍歷** @param paraStartIndex 起始頂點* @return 遍歷序列*/public String depthFirstTraversal(int paraStartIndex){// 初始化棧、儲存遍歷結果的字符串ObjectStack tempStack = new ObjectStack();String resString = "";int tempNumNodes = connectivityMatrix.getRows();boolean[] tempVisitedArray = new boolean[tempNumNodes]; // 標記// 開始遍歷tempVisitedArray[paraStartIndex] = true;resString += paraStartIndex;tempStack.push(paraStartIndex);int tempIndex = paraStartIndex;while (true){int tempNext = -1;for (int i = 0; i < tempNumNodes; i++) {// 已訪問if (tempVisitedArray[i]){continue;}// Of if// 無通路if (connectivityMatrix.getData()[tempIndex][i]==0){continue;}// Of if// 正常訪問tempVisitedArray[i] = true;resString += i;tempStack.push(i);tempNext = i;break;}// Of forif (tempNext == -1){ // 沒有續(xù)上，需出棧if (tempStack.isEmpty()){break;}// Of iftempIndex = (int) tempStack.pop();} else{tempIndex = tempNext;}// Of if}// Of whilereturn resString;}// Of depthFirstTraversal/*** 單元測試 深度遍歷*/public static void depthFirstTraversalTest() {// Test an undirected graph.int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 0}, { 0, 1, 0, 0} };Graph tempGraph = new Graph(tempMatrix);System.out.println(tempGraph);String tempSequence = "";try {tempSequence = tempGraph.depthFirstTraversal(0);} catch (Exception ee) {System.out.println(ee);} // Of try.System.out.println("The depth first order of visit: " + tempSequence);}//Of depthFirstTraversalTest

35.圖的 m 著色問題

    /*** 涂色的所有可能** @param paraNumColors       顏色總數(shù)* @param paraCurrentNumNodes 當前要涂的頂點* @param paraCurrentColoring 當前顏色 數(shù)組*/public void coloring(int paraNumColors, int paraCurrentNumNodes, int[] paraCurrentColoring) {int tempNumNodes = connectivityMatrix.getRows();if (paraCurrentNumNodes >= tempNumNodes) { // 著色完成System.out.println("Find one:" + Arrays.toString(paraCurrentColoring));return;}// 枚舉顏色 暴力解// for:顏色 遞歸:頂點for (int i = 0; i < paraNumColors; i++) {// 涂色paraCurrentColoring[paraCurrentNumNodes] = i;// 不沖突:涂下一個格子; 沖突: 繼續(xù)for循環(huán),換色if (!colorConflict(paraCurrentNumNodes + 1, paraCurrentColoring)) {coloring(paraNumColors, paraCurrentNumNodes + 1, paraCurrentColoring);}// Of if}// Of for}// Of coloring/*** 顏色是否沖突，檢查已經(jīng)著色的所有節(jié)點** @param paraCurrentNumNodes 當前頂點* @param paraColoring 著色數(shù)組* @return true:相鄰節(jié)點顏色相同，沖突; false:沒問題*/public boolean colorConflict(int paraCurrentNumNodes, int[] paraColoring) {for (int i = 0; i < paraCurrentNumNodes - 1; i++) {// 無通路if (connectivityMatrix.getValue(paraCurrentNumNodes - 1, i) == 0) {continue;}// Of if// 有通路: 相鄰，相鄰節(jié)點顏色相同，結束方法if (paraColoring[paraCurrentNumNodes - 1] == paraColoring[i]) {return true;}// Of if}// Of forreturn false;}// Of colorConflict/*** 著色** @param paraNumColors 顏色數(shù)*/public void coloring(int paraNumColors) {// Step 1. Initialize.int tempNumNodes = connectivityMatrix.getRows();int[] tempColorScheme = new int[tempNumNodes];Arrays.fill(tempColorScheme, -1);coloring(paraNumColors, 0, tempColorScheme);}// Of coloring/*** 著色單元測試*/public static void coloringTest() {int[][] tempMatrix = {{0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 0}, {0, 1, 0, 0}};Graph tempGraph = new Graph(tempMatrix);//tempGraph.coloring(2);tempGraph.coloring(3);}// Of coloringTest

有點難度

36.鄰連表

加上了深度遍歷，toString改了改

package day40;import day20.CircleAnyQueue;/*** Day36:鄰接表* * @author pzf*/
public class AdjacencyList {/*** 內(nèi)部類，邊節(jié)點*/class AdjacencyNode {int column; // 編號AdjacencyNode next;  // 下一個邊節(jié)點/*** 構造方法** @param paraColumn 編號*/public AdjacencyNode(int paraColumn) {this.column = paraColumn;this.next = null;}// Of contractor}// Of class AdjacencyNodeint numNodes; // 節(jié)點數(shù)AdjacencyNode[] headers;  // 每個頭結點組成的鏈表/*** 構造方法** @param paraMatrix 圖的鄰接矩陣*/public AdjacencyList(int[][] paraMatrix) {numNodes = paraMatrix.length;AdjacencyNode tempPreviousNode, tempNode;headers = new AdjacencyNode[numNodes];for (int i = 0; i < numNodes; i++) {headers[i] = new AdjacencyNode(-1);tempPreviousNode = headers[i];for (int j = 0; j < numNodes; j++) {// 無通路 跳過if (paraMatrix[i][j] == 0) {continue;}// Of iftempNode = new AdjacencyNode(j);tempPreviousNode.next = tempNode;tempPreviousNode = tempNode;}// Of for j}// Of for i}// Of contractor/*** 重寫toString** @return 字符串*/public String toString() {String resultString = "";AdjacencyNode tempNode;for (int i = 0; i < numNodes; i++) {tempNode = headers[i].next;resultString += i + "->";if (tempNode == null) {resultString += " \\";} else {while (tempNode != null) {resultString += " (" + tempNode.column + ")";tempNode = tempNode.next;} // Of while}resultString += "\r\n";} // Of for ireturn resultString;}// Of toString// 遍歷/*** 廣度遍歷** @param paraStartIndex 起始節(jié)點* @return 遍歷字符串*/public String breadthFirstTraversal(int paraStartIndex) {String resString = "";CircleAnyQueue<Integer> tempQueue = new CircleAnyQueue<>();boolean[] tempMarkArray = new boolean[this.numNodes];// 處理起始點tempMarkArray[paraStartIndex] = true;resString += paraStartIndex;tempQueue.enqueue(paraStartIndex);AdjacencyNode tempNode;Integer tempInteger = tempQueue.dequeue();while (tempInteger != null) {//resString += tempInteger;tempNode = headers[tempInteger].next;// 廣度while (tempNode != null) {// 是否訪問過if (!tempMarkArray[tempNode.column]) {tempMarkArray[tempNode.column] = true;resString += tempNode.column;tempQueue.enqueue(tempNode.column);}// Of iftempNode = tempNode.next;}// Of whiletempInteger = tempQueue.dequeue();}// Of whilereturn resString;}// Of breadthFirstTraversal/*** 深度遍歷** @param paraStartIndex 起始節(jié)點* @return 遍歷字符串*/public String depthFirstTraversal(int paraStartIndex) {String resString = "";CircleAnyQueue<Integer> tempQueue = new CircleAnyQueue<>();boolean[] tempMarkArray = new boolean[this.numNodes];// 處理起始點tempMarkArray[paraStartIndex] = true;resString += paraStartIndex;tempQueue.enqueue(paraStartIndex);boolean flag; // 標記位AdjacencyNode tempNode;Integer tempInteger = paraStartIndex;while (tempInteger != null) {flag = false;tempNode = headers[tempInteger].next;while (tempNode != null) {flag = true; // 判斷是否需要出隊if (!tempMarkArray[tempNode.column]){resString += tempNode.column;tempMarkArray[tempNode.column] = true;tempQueue.enqueue(tempNode.column);tempInteger = tempNode.column;break;}// Of iftempNode = tempNode.next;}// Of whileif (!flag || tempNode==null){tempInteger = tempQueue.dequeue();}// Of if}// Of whilereturn resString;}// Of depthFirstTraversal/*** 單元測試*/public static void adTest(){int[][] dataMatrix1 = {{0, 1, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}};int[][] dataMatrix2 = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 }, { 0, 1, 1, 0 } };AdjacencyList list1 = new AdjacencyList(dataMatrix1);AdjacencyList list2 = new AdjacencyList(dataMatrix2);System.out.println(list1);System.out.println(list1.breadthFirstTraversal(2));System.out.println(list1.depthFirstTraversal(3));System.out.println("\n");System.out.println(list2);System.out.println(list2.breadthFirstTraversal(2));System.out.println(list2.depthFirstTraversal(3));}/*** main* * @param args*/public static void main(String[] args) {//int[][] dataMatrix = {{0, 1, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}};adTest();}
}// Of class AdjacencyList

37.十字鏈表

package day40;/*** Day37: 十字鏈表* * @author pzf*/
public class OrthogonalList {/*** 內(nèi)部類，鄰接節(jié)點*/class OrthogonalNode{int row; // 行int column; // 列OrthogonalNode nextIn; // 下一個入邊OrthogonalNode nextOut;// 下一個出邊/*** 構造方法** @param paraRow 行* @param paraColumn 列*/public OrthogonalNode(int paraRow, int paraColumn) {row = paraRow;column = paraColumn;nextOut = null;nextIn = null;}// Of contractor}// Of class OrthogonalNodeOrthogonalNode[] headers; // 頭結點數(shù)組int numNodes; // 節(jié)點數(shù)量/*** 構造方法* 通過鄰接矩陣生成十字鏈表** @param paraMatrix 鄰接矩陣*/public OrthogonalList(int[][] paraMatrix){numNodes = paraMatrix.length;OrthogonalNode tempPreviousNode, tempNode;headers = new OrthogonalNode[numNodes];// 每個頭結點遍歷for (int i = 0; i < numNodes; i++) {headers[i] = new OrthogonalNode(i,-1);tempPreviousNode = headers[i];// 出邊for (int j = 0; j < numNodes; j++) {if (paraMatrix[i][j]==0){continue;}// Of iftempNode = new OrthogonalNode(i,j);tempPreviousNode.nextOut = tempNode;tempPreviousNode = tempNode;}// Of for j}// Of for iOrthogonalNode[] tempColumnNodes = new OrthogonalNode[numNodes];// 復制System.arraycopy(headers, 0, tempColumnNodes, 0, numNodes);// 入邊for (int i = 0; i < numNodes; i++) {tempNode = headers[i].nextOut;while (tempNode!=null){tempColumnNodes[tempNode.column].nextIn = tempNode;tempColumnNodes[tempNode.column] = tempNode;tempNode = tempNode.nextOut;}// Of while}// Of for}// Of contractor/*** 重寫toString* * @return 字符串*/public String toString() {String resultString = "Out arcs: ";OrthogonalNode tempNode;for (int i = 0; i < numNodes; i++) {tempNode = headers[i].nextOut;while (tempNode != null) {resultString += " (" + tempNode.row + ", " + tempNode.column + ")";tempNode = tempNode.nextOut;} // Of whileresultString += "\r\n";} // Of for iresultString += "\r\nIn arcs: ";for (int i = 0; i < numNodes; i++) {tempNode = headers[i].nextIn;while (tempNode != null) {resultString += " (" + tempNode.row + ", " + tempNode.column + ")";tempNode = tempNode.nextIn;} // Of whileresultString += "\r\n";} // Of for ireturn resultString;}// Of toString/*** main* * @param args*/public static void main(String args[]) {int[][] tempMatrix = { { 0, 1, 0, 0 }, { 0, 0, 0, 1 }, { 1, 0, 0, 0 }, { 0, 1, 1, 0 } };OrthogonalList tempList = new OrthogonalList(tempMatrix);System.out.println("The data are:\r\n" + tempList);}// Of main
}// Of class OrthogonalList

38.Dijkstra 算法與 Prim 算法

package day40;import java.util.Arrays;public class Net {// 可替換 Integer.MAX_VALUEpublic static final int MAX_DISTANCE = 10000;int numNodes; // 頂點數(shù)IntMatrix weightMatrix; // 權重矩陣/*** 構造方法1,給定頂點數(shù),用MAX_DISTANCE填充** @param paraNumNodes 頂點數(shù)*/public Net(int paraNumNodes) {numNodes = paraNumNodes;weightMatrix = new IntMatrix(numNodes, numNodes);for (int i = 0; i < numNodes; i++) {Arrays.fill(weightMatrix.getData()[i], MAX_DISTANCE);}// Of for i}// Of the first contractor/*** 構造方法2,給定鄰接矩陣.** @param paraMatrix 鄰接矩陣*/public Net(int[][] paraMatrix) {weightMatrix = new IntMatrix(paraMatrix);numNodes = weightMatrix.getRows();}// Of the second contractorpublic String toString() {return this.weightMatrix.toString();}/*** Dijkstra,得到起始點到各個頂點的最短距離.** @param paraSource 起始點.* @return 到各個點最短距離的數(shù)組.*/public int[] dijkstra(int paraSource) {// 1.1 初始化Dist數(shù)組，記錄起始點到各點的初始路徑.int[] tempDistArray = new int[this.numNodes];for (int i = 0; i < numNodes; i++) {tempDistArray[i] = weightMatrix.getValue(paraSource, i);}// Of for i// 1.2 初始化Path數(shù)組，記錄最短路徑的前驅(qū)結點.int[] tempParentArray = new int[numNodes];Arrays.fill(tempParentArray, paraSource);tempParentArray[paraSource] = -1;// 1.3 初始化瀏覽數(shù)組，記錄對應頂點是否找到最短路徑.boolean[] tempVisitedArray = new boolean[numNodes];tempVisitedArray[paraSource] = true;int tempMinDistance;int tempBestNode = -1;for (int i = 0; i < numNodes - 1; i++) {tempMinDistance = Integer.MAX_VALUE;// 2.1 找到最小的路徑,頂點for (int j = 0; j < numNodes; j++) {if (tempVisitedArray[j]) { // 已經(jīng)訪問continue;}// Of if// 更小，替換if (tempMinDistance > tempDistArray[j]) {tempMinDistance = tempDistArray[j];tempBestNode = j;}// Of if}// Of for jtempVisitedArray[tempBestNode] = true;// For testSystem.out.println("The distance to each node: " + Arrays.toString(tempDistArray));System.out.println("The parent of each node: " + Arrays.toString(tempParentArray) + "\n");// 2.2 為下一輪做準備，更新距離for (int j = 0; j < numNodes; j++) {// 已經(jīng)確定，跳過if (tempVisitedArray[j]) {continue;}// Of if// 無法到達，跳過if (this.weightMatrix.getValue(tempBestNode, j) >= MAX_DISTANCE) {continue;}// Of if// 新路徑更短，更新if (tempDistArray[j] > tempDistArray[tempBestNode]+ this.weightMatrix.getValue(tempBestNode, j)) {tempDistArray[j] = tempDistArray[tempBestNode]+ this.weightMatrix.getValue(tempBestNode, j);// 更新前驅(qū)tempParentArray[j] = tempBestNode;}// Of if}// Of for j// For test//System.out.println("The distance to each node: " + Arrays.toString(tempDistArray));//System.out.println("The parent of each node: " + Arrays.toString(tempParentArray)+"\n");}// Of for ireturn tempDistArray;}// Of dijkstra/*** Prim.** @return 最小權值和*/public int prim() {// 無向圖判斷if (!this.weightMatrix.isUndirected()){System.out.println("Not undirected graph.");return -1;}// Of if// 1.1 初始化Dist數(shù)組, 記錄當前距離int tempSource = 0; // 初始節(jié)點設為0 (任意都可)int[] tempDistArray = new int[numNodes];for (int i = 0; i < numNodes; i++) {tempDistArray[i] = weightMatrix.getValue(tempSource, i);}// Of for i// 1.2 初始化Path數(shù)組, 記錄父節(jié)點int[] tempParentArray = new int[numNodes];Arrays.fill(tempParentArray, tempSource);tempParentArray[0] = -1;// 1.3 標記數(shù)組boolean[] tempVisitedArray = new boolean[numNodes];tempVisitedArray[tempSource] = true;int tempMinDistance;int tempBestNode = -1;for (int i = 0; i < numNodes - 1; i++) {tempMinDistance = Integer.MAX_VALUE;// 2.1 找最小for (int j = 0; j < numNodes; j++) {if (tempVisitedArray[j]){continue;}// Of ifif (tempMinDistance > tempDistArray[j]) {tempMinDistance = tempDistArray[j];tempBestNode = j;}// Of if}tempVisitedArray[tempBestNode] = true;// DebugSystem.out.println("The parent of each node: " + Arrays.toString(tempParentArray));System.out.println("The dist of each node: " + Arrays.toString(tempDistArray) + "\n");// 2.2 更新Dist Parentfor (int j = 0; j < numNodes; j++) {if (tempVisitedArray[j]){continue;}// Of ifif (weightMatrix.getValue(tempBestNode, j) >= MAX_DISTANCE) {continue;} // Of ifif (tempDistArray[j] > weightMatrix.getValue(tempBestNode, j)) {tempDistArray[j] = weightMatrix.getValue(tempBestNode, j);tempParentArray[j] = tempBestNode;} // Of if}// Of for j}// Of for i// 3. 權值和int resCost = 0;for (int i = 0; i < numNodes; i++) {resCost += tempDistArray[i];}// Of for ireturn resCost;}// Of primpublic static void main(String[] args) {int[][] tempMatrix1 = {{0, 10, MAX_DISTANCE, MAX_DISTANCE, 5},{MAX_DISTANCE, 0, 1, MAX_DISTANCE, 2}, {MAX_DISTANCE, MAX_DISTANCE, 0, 4, MAX_DISTANCE}, {7,MAX_DISTANCE, 6, 0, MAX_DISTANCE}, {MAX_DISTANCE, 3, 9, 2, 0}};Net tempNet1 = new Net(tempMatrix1);System.out.println(tempNet1);// DijkstratempNet1.dijkstra(0);int[][] tempMatrix2 = {{0, 7, MAX_DISTANCE, 5, MAX_DISTANCE}, {7, 0, 8, 9, 7},{MAX_DISTANCE, 8, 0, MAX_DISTANCE, 5}, {5, 9, MAX_DISTANCE, 0, 15},{MAX_DISTANCE, 7, 5, 15, 0}};Net tempNet2 = new Net(tempMatrix2);System.out.println("Prim:");System.out.println("The cost:" + tempNet2.prim());}
}

class IntMatrix加上無向圖判斷方法：

	/*** 判斷是否為無向圖(鄰接矩陣對稱)** @return 是: true, 否: false.*/public boolean isUndirected(){int numNodes = this.getRows();int[][] tempMatrix = this.getData();for (int i = 1; i < numNodes; i++) {for (int j = 0; j < i; j++) {if (tempMatrix[i][j] != tempMatrix[j][i]){return false;}// Of if}// Of for j}// Of for ireturn true;}// Of isUndirected

[[0, 10, 10000, 10000, 5], [10000, 0, 1, 10000, 2], [10000, 10000, 0, 4, 10000], [7, 10000, 6, 0, 10000], [10000, 3, 9, 2, 0]]
The distance to each node: [0, 10, 10000, 10000, 5]
The parent of each node: [-1, 0, 0, 0, 0]The distance to each node: [0, 8, 14, 7, 5]
The parent of each node: [-1, 4, 4, 4, 0]The distance to each node: [0, 8, 13, 7, 5]
The parent of each node: [-1, 4, 3, 4, 0]The distance to each node: [0, 8, 9, 7, 5]
The parent of each node: [-1, 4, 1, 4, 0]Prim:
The parent of each node: [-1, 0, 0, 0, 0]
The dist of each node: [0, 7, 10000, 5, 10000]The parent of each node: [-1, 0, 0, 0, 3]
The dist of each node: [0, 7, 10000, 5, 15]The parent of each node: [-1, 0, 1, 0, 1]
The dist of each node: [0, 7, 8, 5, 7]The parent of each node: [-1, 0, 4, 0, 1]
The dist of each node: [0, 7, 5, 5, 7]The cost:24Process finished with exit code 0

---

隨緣學習ing