用dw制作网站建设最大的搜索网站排名

日撸代码300行（31-40天，图）

原文：日撸代码300行（31-40天，图）_minfanphd的博客-CSDN博客

31.整数矩阵及其运算

package day40;import day10.MatrixMultiplication;import java.util.Arrays;/*** Day 31 整数矩阵** @author pzf*/
public class IntMatrix {// 变量int[][] data; // 二维数组/*** 构造方法1** @param paraRows    行* @param paraColumns 列*/public IntMatrix(int paraRows, int paraColumns) {this.data = new int[paraRows][paraColumns];}// Of the first contractor/*** 构造方法2 复制数组** @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 单位矩阵的行列数* @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$的边数，称$(a_{ij}^{(1)}{)}_{m\times n}$为$D$的邻接矩阵，记作$A(D)$，简记为$A$.

定理1：$A$的$l$次幂$A^l$中元素$a_{ij}^{(l)}$为$D$中$v_i$到$v_j$长度为$l$的通路数。

证明：$l=1$时，根据邻接矩阵定义，$a_{ij}^{(1)}$等于$v_i$到$v_j$长度为1的通路数，结论成立。
假设对$l$成立，即$a_{ij}^{(l)}$等于$v_i$到$v_j$长度为$l$的通路数，要证结论对$l+1$成立。
因为$v_i$到$v_j$长度为$l+1$的一条通路由$v_i$到某一点$v_k$的通路加$v_k$到$v_j$的一条边组成，根据归纳假设，$v_i$到$v_k$长度为$l$的通路数等于$a_{ik}^{(l)}$，所以$v_i$到$v_j$长度为$l+1$的通路数等于
$$\sum _{k=1}^n{a}_{ik}^{(l)}\cdot 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$的通路数。

定义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\ne 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}$

参考自《离散数学》

package day40;/*** Day 32:有向图，无向图作为其中一种特殊情况** @author pzf*/
public class Graph {IntMatrix connectivityMatrix;/*** 构造方法** @param paraNumNodes 顶点数*/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);// 指数+1temMultipliedMatrix = IntMatrix.multiplyMatrix(temMultipliedMatrix,connectivityMatrix);}// Of for// 4.判断联通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.图的广度优先遍历

    /*** 广度遍历** @param paraStartIndex 起始点* @return 遍历字符串*/public String breadthFirstTraversal(int paraStartIndex) {// 初始化队列、字符串AnyQueue tempQueue = new AnyQueue();String resString = "";// 获取节点数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;// 遍历节点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;// 拼接该节点resString += i;// 入队tempQueue.enqueue(i);}// Of for// 出队 访问剩余节点时用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还是会自动转换Integer和int.

34.图的深度优先遍历

/*** 深度优先遍历** @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){ // 没有续上，需出栈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       颜色总数* @param paraCurrentNumNodes 当前要涂的顶点* @param paraCurrentColoring 当前颜色 数组*/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;// 不冲突:涂下一个格子; 冲突: 继续for循环,换色if (!colorConflict(paraCurrentNumNodes + 1, paraCurrentColoring)) {coloring(paraNumColors, paraCurrentNumNodes + 1, paraCurrentColoring);}// Of if}// Of for}// Of coloring/*** 颜色是否冲突，检查已经着色的所有节点** @param paraCurrentNumNodes 当前顶点* @param paraColoring 着色数组* @return true:相邻节点颜色相同，冲突; 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// 有通路: 相邻，相邻节点颜色相同，结束方法if (paraColoring[paraCurrentNumNodes - 1] == paraColoring[i]) {return true;}// Of if}// Of forreturn false;}// Of colorConflict/*** 着色** @param paraNumColors 颜色数*/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 {/*** 内部类，边节点*/class AdjacencyNode {int column; // 编号AdjacencyNode next;  // 下一个边节点/*** 构造方法** @param paraColumn 编号*/public AdjacencyNode(int paraColumn) {this.column = paraColumn;this.next = null;}// Of contractor}// Of class AdjacencyNodeint numNodes; // 节点数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 起始节点* @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 起始节点* @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 {/*** 内部类，邻接节点*/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; // 头结点数组int numNodes; // 节点数量/*** 构造方法* 通过邻接矩阵生成十字链表** @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; // 顶点数IntMatrix weightMatrix; // 权重矩阵/*** 构造方法1,给定顶点数,用MAX_DISTANCE填充** @param paraNumNodes 顶点数*/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 到各个点最短距离的数组.*/public int[] dijkstra(int paraSource) {// 1.1 初始化Dist数组，记录起始点到各点的初始路径.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数组，记录最短路径的前驱结点.int[] tempParentArray = new int[numNodes];Arrays.fill(tempParentArray, paraSource);tempParentArray[paraSource] = -1;// 1.3 初始化浏览数组，记录对应顶点是否找到最短路径.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]) { // 已经访问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++) {// 已经确定，跳过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);// 更新前驱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数组, 记录当前距离int tempSource = 0; // 初始节点设为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数组, 记录父节点int[] tempParentArray = new int[numNodes];Arrays.fill(tempParentArray, tempSource);tempParentArray[0] = -1;// 1.3 标记数组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