- Java 图（一）
- 一、整数矩阵及其运算
- 二、图的连通性检测
学习来源： 日撸 Java 三百行（31-40天，图） 一、整数矩阵及其运算
这个代码以前有基础. 原想着写矩阵连通性, 把这个当成开胃菜的, 后来发现这个的代码量已经够了. 良心发现, 把这个做成一天的工作.
- 矩阵对象的创建.
- getRows 等: getter, setter 在 java 里面很常用. 主要是为了访问控制.
- 整数矩阵的加法、乘法.
- Exception 的抛出与捕获机制.
- 用 this 调用其它的构造方法以减少冗余代码.
- 代码看起来多, 但矩阵运算我们以前写过.
- 把数据类型修改成 double, 获得 DoubleMatrix.java, 以后会很有用.
- getIdentityMatrix: 单位矩阵.
- resultMatrix.data[i][i]: 成员变量的访问权限: 在同一类里面是可以直接使用的.
题目一：矩阵相加
输入：
两个矩阵
输出：
给定矩阵相加之后得到的新矩阵
题目二：矩阵相乘
输入：
两个矩阵
输出：
给定矩阵相乘之后得到的新矩阵
package matrix;
import java.util.Arrays;
/**
*
* @author Ling Lin E-mail:[email protected]
*
* @version 创建时间：2022年4月23日 下午4:52:33
*
*/
public class IntMatrix {
// The data.
int[][] data;
/**
* The first constructor.
*
* @param paraRows
* The number of rows.
* @param paraColumns
* The number of columns.
*/
public IntMatrix(int paraRows, int paraColumns) {
data = new int[paraRows][paraColumns];
}// Of the first constructor
/**
* The second constructor. Construct a copy of the given matrix.
*
* @param paraMatrix
* The given matrix.
*/
public IntMatrix(int[][] paraMatrix) {
data = new int[paraMatrix.length][paraMatrix[0].length];
// Copy elements.
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data[0].length; j++) {
data[i][j] = paraMatrix[i][j];
} // Of for j
} // Of for i
}// Of the second constructor
/**
* The third constructor. Construct a copy of the given matrix.
*
* @param paraMatrix
* The given matrix.
*/
public IntMatrix(IntMatrix paraMatrix) {
this(paraMatrix.getData());
}// Of the third constructor
/**
* Get identity matrix. The values at the diagonal are all 1.
*
* @param paraRows
* The given rows.
*/
public static IntMatrix getIdentityMatrix(int paraRows) {
IntMatrix resultMatrix = new IntMatrix(paraRows, paraRows);
for (int i = 0; i < paraRows; i++) {
// According to access control, resultMatrix.data can be visited
// directly.
resultMatrix.data[i][i] = 1;
} // Of for i
return resultMatrix;
}// Of getIdentityMatrix
/**
* Overrides the method claimed in Object, the superclass of any class.
*
*/
@Override
public String toString() {
return Arrays.deepToString(data);
}// Of toString
/**
* Get my data. Warning, the reference to the data instead of a copy of the
* data is returned.
*
* @return The data matrix.
*/
public int[][] getData() {
return data;
}// Of getData
/**
* Getter.
*
* @return The number of rows.
*/
public int getRows() {
return data.length;
}// Of getRows
/**
* Getter.
*
* @return The number of columns.
*/
public int getColumns() {
return data[0].length;
}// Of getColumns
/**
* Set one the value of one element.
*
* @param paraRow
* The row of the element.
* @param paraColumn
* The column of the element.
* @param paraValue
* The new value.
*/
public void setValue(int paraRow, int paraColumn, int paraValue) {
data[paraRow][paraColumn] = paraValue;
}// Of setValue
/**
* Get the value of one element.
*
* @param paraRow
* The row of the element.
* @param paraColumn
* The column of the element.
*/
public int getValue(int paraRow, int paraColumn) {
return data[paraRow][paraColumn];
}// Of getValue
/**
* Add another matrix to me.
*
* @param paraMatrix
* The other matrix.
*/
public void add(IntMatrix paraMatrix) throws Exception {
// Step 1. Get the data of the given matrix.
int[][] tempData = paraMatrix.getData();
// Step 2. Size check.
if (data.length != tempData.length) {
throw new Exception(
"Cannot add matrices. Rows not match: " + data.length + " vs. " + tempData.length + ".");
} // Of if
if (data[0].length != tempData[0].length) {
throw new Exception(
"Cannot add matrices. Columns not match: " + data[0].length + " vs. " + tempData[0].length + ".");
} // Of if
// Step 3. Add to me.
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data[0].length; j++) {
data[i][j] += tempData[i][j];
} // Of for j
} // Of for i
}// Of add
/**
* Add two existing matrices.
*
* @param paraMatrix1
* The first matrix.
* @param paraMatrix2
* The second matrix.
* @return A new matrix.
*/
public static IntMatrix add(IntMatrix paraMatrix1, IntMatrix paraMatrix2) throws Exception {
// Step 1. Clone the first matrix.
IntMatrix resultMatrix = new IntMatrix(paraMatrix1);
// Step 2. Add the second one.
resultMatrix.add(paraMatrix2);
return resultMatrix;
}// Of add
/**
* Multiply two existing matrices.
*
* @param paraMatrix1
* The first matrix.
* @param paraMatrix2
* The second matrix.
* @return A new matrix.
*/
public static IntMatrix multiply(IntMatrix paraMatrix1, IntMatrix paraMatrix2) throws Exception {
// Step 1. Check size.
int[][] tempData1 = paraMatrix1.getData();
int[][] tempData2 = paraMatrix2.getData();
if (tempData1[0].length != tempData2.length) {
throw new Exception("Cannot multiply matrices: " + tempData1[0].length + " vs. " + tempData2.length + ".");
} // Of if
// Step 2. Allocate space.
int[][] resultData = new int[tempData1.length][tempData2[0].length];
// Step 3. Multiply.
for (int i = 0; i < tempData1.length; i++) {
for (int j = 0; j < tempData2[0].length; j++) {
for (int k = 0; k < tempData1[0].length; k++) {
resultData[i][j] += tempData1[i][k] * tempData2[k][j];
} // Of for k
} // Of for j
} // Of for i
// Step 4. Construct the matrix object.
IntMatrix resultMatrix = new IntMatrix(resultData);
return resultMatrix;
}// Of multiply
/**
* The entrance of the program.
*
* @param args
* Not used now.
*/
public static void main(String args[]) {
IntMatrix tempMatrix1 = new IntMatrix(3, 3);
tempMatrix1.setValue(0, 1, 1);
tempMatrix1.setValue(1, 0, 1);
tempMatrix1.setValue(1, 2, 1);
tempMatrix1.setValue(2, 1, 1);
System.out.println("The original matrix is： " + tempMatrix1);
IntMatrix tempMatrix2 = null;
try {
tempMatrix2 = IntMatrix.multiply(tempMatrix1, tempMatrix1);
} catch (Exception ee) {
System.out.println(ee);
} // Of try
System.out.println("The square matrix is： " + tempMatrix2);
IntMatrix tempMatrix3 = new IntMatrix(tempMatrix2);
try {
tempMatrix3.add(tempMatrix1);
} catch (Exception ee) {
System.out.println(ee);
} // Of try
System.out.println("The connectivity matrix is： " + tempMatrix3);
}// Of main
}// Of class IntMatrix
运行截图：
- 适用于有向图. 反正无向图是有向图的特殊形式.
- 0 次方的时候是单位矩阵.
- 为每一个方法写一个独立的测试方法. 测试代码有时比正常使用的代码更多.
- 第一个测试用例是无向图, 第二个是有向图. 可以看到, 后者从节点 1 不能到达节点 0.
- Matrix 基础代码准备好之后, 其它的算法真的很方便. 后面会进一步体会到其威力.
代码如下：
package datastructure.graph;
import matrix.IntMatrix;
/**
*
* @author Ling Lin E-mail:[email protected]
*
* @version 创建时间：2022年4月23日 下午7:29:14
*
*/
public class Graph {
// The connectivity matrix.
IntMatrix connectivityMatrix;
/**
* The first constructor
*
* @param paraNumNodes
* The number of nodes in the graph.
*/
public Graph(int paraNumNodes) {
connectivityMatrix = new IntMatrix(paraNumNodes, paraNumNodes);
}// Of the first constructor
/**
* The second constructor.
*
* @param paraMatrix
* The data matrix.
*/
public Graph(int[][] paraMatrix) {
connectivityMatrix = new IntMatrix(paraMatrix);
}// Of the second constructor
/**
* Overrides the method claimed in Object, the superclass of any class.
*/
@Override
public String toString() {
String resultString = "This is the connectivity matrix of the graph.\r\n" + connectivityMatrix;
return resultString;
}// Of toString
/**
* Get the connectivity of the graph.
*
* @throws Exception
* for internal error.
*/
public boolean getConnectivity() throws Exception {
// Step 1. Initialize accumulated matrix: M_a = I.
IntMatrix tempConnectivityMatrix = IntMatrix.getIdentityMatrix(connectivityMatrix.getData().length);
// Step 2. Initialize M^1.
IntMatrix tempMultipliedMatrix = new IntMatrix(connectivityMatrix);
// Step 3. Determine the actual connectivity.
for (int i = 0; i < connectivityMatrix.getData().length - 1; i++) {
// M_a = M_a + M^k
tempConnectivityMatrix.add(tempMultipliedMatrix);
// M^k
tempMultipliedMatrix = IntMatrix.multiply(tempMultipliedMatrix, connectivityMatrix);
} // Of for i
// Step 4. Check the connectivity.
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 i
return true;
}// Of getConnectivity
/**
* Unit test for 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);
// Test a directed graph.
// Remove one arc to form a directed graph.
tempGraph2.connectivityMatrix.setValue(1, 0, 0);
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
/**
* The entrance of the program.
*
* @param args
* Not used now.
*/
public static void main(String args[]) {
System.out.println("Hello!");
Graph tempGraph = new Graph(3);
System.out.println(tempGraph);
// Unit test.
getConnectivityTest();
}// Of main
}// Of class Graph
**
**
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）