做网站的困难,手机上的应用商店,微信小程序开发工具下载哪个版本,嘉兴网站制作价格日撸代码300行#xff08;31-40天#xff0c;图#xff09;
原文#xff1a;日撸代码300行#xff08;31-40天#xff0c;图#xff09;_minfanphd的博客-CSDN博客 目录 日撸代码300行#xff08;31-40天#xff0c;图#xff09;31.整数矩阵及其运算32.图的连通性检…日撸代码300行31-40天图
原文日撸代码300行31-40天图_minfanphd的博客-CSDN博客 目录 日撸代码300行31-40天图31.整数矩阵及其运算32.图的连通性检测32.1 如何判断连通性33.图的广度优先遍历34.图的深度优先遍历35.图的 m 着色问题36.邻连表37.十字链表38.Dijkstra 算法与 Prim 算法 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 (tempArraynull){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 i j ( 1 ) a_{ij}^{(1)} aij(1)为顶点 v i v_i vi到顶点 v j v_j vj的边数称 ( a i j ( 1 ) ) m × n (a_{ij}^{(1)})_{m\times n} (aij(1))m×n为 D D D的邻接矩阵记作 A ( D ) A(D) A(D)简记为 A A A.
定理1 A A A的 l l l次幂 A l A^l Al中元素 a i j ( l ) a_{ij}^{(l)} aij(l)为 D D D中 v i v_i vi到 v j v_j vj长度为 l l l的通路数。
证明 l 1 l1 l1时根据邻接矩阵定义 a i j ( 1 ) a_{ij}^{(1)} aij(1)等于 v i v_i vi到 v j v_j vj长度为1的通路数结论成立。 假设对 l l l成立即 a i j ( l ) a_{ij}^{(l)} aij(l)等于 v i v_i vi到 v j v_j vj长度为 l l l的通路数要证结论对 l 1 l1 l1成立。 因为 v i v_i vi到 v j v_j vj长度为 l 1 l1 l1的一条通路由 v i v_i vi到某一点 v k v_k vk的通路加 v k v_k vk到 v j v_j vj的一条边组成根据归纳假设 v i v_i vi到 v k v_k vk长度为 l l l的通路数等于 a i k ( l ) a_{ik}^{(l)} aik(l)所以 v i v_i vi到 v j v_j vj长度为 l 1 l1 l1的通路数等于 ∑ k 1 n a i k ( l ) ⋅ a k j ( 1 ) a i j ( l 1 ) \sum\limits_{k1}^{n}a_{ik}^{(l)}\cdot a_{kj}^{(1)} a_{ij}^{(l1)} k1∑naik(l)⋅akj(1)aij(l1) 得证对 l 1 l1 l1结论成立。
推论设 B l A A 2 . . . A l ( l ≥ 1 ) B_lAA^2...A^l(l\ge1) BlAA2...Al(l≥1) B l B_l Bl中元素之和 ∑ i 1 n ∑ j 1 n b i j ( l ) \sum\limits_{i1}^{n}\sum\limits_{j1}^{n}b_{ij}^{(l)} i1∑nj1∑nbij(l)为 D D D中长度小于等于 l l 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 i j { 1 , v i 可 达 v j 0 , 否 则 p_{ij} \left\{ \begin{aligned} 1, v_i可达v_j \\ 0, 否则 \\ \end{aligned} \right. pij{1,0,vi可达vj否则 称 ( p i j ) m × n (p_{ij})_{m\times n} (pij)m×n为 D D D的可达矩阵记作 P ( D ) P(D) P(D)简记为 P P P.
定理2在 n n n阶图 G G G中若从顶点 u u u到 v v v ( u ≠ v ) (u\neq v) (uv)存在通路则从 u u u到 v v v存在长度小于等于 n − 1 n-1 n−1的通路。
由定理2和定理1的推论可知只要计算出 B n − 1 B_{n-1} Bn−1由 B n − 1 B_{n-1} Bn−1的元素 b i j ( n − 1 ) b_{ij}^{(n-1)} bij(n−1)是否为0就可以写出 D D D的可达矩阵。不过 p i i p_{ii} pii总为1与 B n − 1 B_{n-1} Bn−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 Graph33.图的广度优先遍历 /*** 广度遍历** 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 depthFirstTraversalTest35.图的 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 ;CircleAnyQueueInteger 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 ;CircleAnyQueueInteger 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 || tempNodenull){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
