一:矩阵的基础运算:
先来编写一段矩阵相乘和相加以及初始化的代码(后面附上结果图),以此为基础,开启图的学习:
package matrix;
import java.util.Arrays;
public class IntMatrix {
int data[][];
public IntMatrix(int row, int colunm) {
data = new int[row][colunm];
}// 规定行列初始化。
public IntMatrix(int[][] temp) {
data = new int[temp.length][temp[0].length];
for (int i = 0; i < temp.length; i++) {
for (int j = 0; j < temp[0].length; j++) {
data[i][j] = temp[i][j];
}
}
}// 使用二维数组初始化
public IntMatrix(IntMatrix matrix) {
this(matrix.getData());
}// 使用矩阵进行初始化。
public int GetRows() {
return data.length;
}
public int GetColumns() {
return data[0].length;
}// 获取长度
public String toString() {
return Arrays.deepToString(data);
}// 打印二维数组
public void setValue(int row, int column, int elem) {
// if(row>data.length||column>data[0].length||row<=0||column<=0) {
// System.out.println("Input Error!");
// return;
// }
data[row - 1][column - 1] = elem;
}// 设置二维数组某一位置的值
public int getValue(int row, int column) {
return data[row - 1][column - 1];
}
public int[][] getData() {
return data;
}// 返回数组
public void add(IntMatrix temp) throws Exception {
int[][] te = temp.getData();
if (this.data.length != te.length) {
throw new Exception("行关系不满足矩阵相加条件");
}
if (this.data[0].length != te[0].length) {
throw new Exception("列关系不满足矩阵相加条件");
}
for (int i = 0; i < te.length; i++) {
for (int j = 0; j < te[0].length; j++) {
this.data[i][j] += te[i][j];
}
}
}// c语言的话,这里就要给两个矩阵参数,相加。java这里可以直接this利用对象直接相加。
// 上一个势必要有对象,而下面这个直接是两个矩阵相加。
public static IntMatrix add(IntMatrix a1, IntMatrix a2) {
IntMatrix temp = a1;
try {
temp.add(a2);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return temp;
}
// 接下来是矩阵相乘,相乘就不一定要求同型了,所以row和column可以不相同。
public static IntMatrix Multiple(IntMatrix a1,IntMatrix a2) throws Exception{
if(a1.data[0].length!=a2.data.length) {
throw new Exception("不满足矩阵相乘的条件!");
}
int[][] atemp1 = a1.getData();
int[][] atemp2 = a2.getData();
int temp = 0;
int[][] result = new int[atemp1.length][atemp2[0].length];//作为结果的矩阵。
for(int i = 0;i<atemp1.length;i++) {
//先获取前一个矩阵的元素,之后获取另一个矩阵的?
for(int j = 0;j<atemp2[0].length;j++) {
for(int k = 0;k<atemp1[0].length;k++) {
result[i][j] += atemp1[i][k]*atemp2[k][j];
}
}
}
IntMatrix resultMatrix = new IntMatrix(result);
return resultMatrix;
}
public static IntMatrix getIdentityMatrix(int pararows) {
IntMatrix temp = new IntMatrix(pararows, pararows);
for (int i = 0; i < pararows; i++) {
temp.data[i][i] = 1;// 这里必须是temp的数组才行。
}
return temp;
}//得到单位矩阵。
public void show() {
int[][] temp = this.getData();
for(int i = 0;i<temp.length;i++) {
for(int j = 0;j<temp[0].length;j++) {
System.out.print(temp[i][j]+" ");
}
System.out.println("");
}
}
//进行简单的测试。
public static void main(String[] args) {
int[][] arr1 = new int[2][3];
for(int i = 0;i<arr1.length;i++) {
for(int j = 0;j<arr1[0].length;j++) {
arr1[i][j] = 1;
}
}
int[][] arr2 = new int[3][2];
for(int i = 0;i<arr2.length;i++) {
for(int j = 0;j<arr2[0].length;j++) {
arr2[i][j] = 1;
}
}
IntMatrix a1 = new IntMatrix(arr1);
System.out.println("a1的矩阵");
a1.show();
IntMatrix a2 = new IntMatrix(arr2);
System.out.println("a2的矩阵");
a2.show();
try {
a1.add(a1);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("a1自身相加后:");
a1.show();
System.out.println("a1和a2相乘后:");
try {
Multiple(a1,a2).show();;
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}//main方法进行测试
}
a1的矩阵
1 1 1
1 1 1
a2的矩阵
1 1
1 1
1 1
a1自身相加后:
2 2 2
2 2 2
a1和a2相乘后:
6 6
6 6
这里唯一需要注意的就是矩阵相乘可能会越界,方法可能没有写对,注意是不是参数啥的写重复了。
二:检测图的连通性:
图的连通性这里需要用到之前矩阵写的那些方法,思路理解之后就很简单,要是有离散数学方面的知识的话,看起来更简单。
中间进行连通性检测的代码要仔细,不然可能会在逻辑上出现错误,比如一直在乘单位矩阵,会造成判断结果出错。
package graph;
import matrix.*;//这就是那个矩阵的基础运算的包,是我自己写的,不是java自带的。
public class Graph {
IntMatrix fgh;
public Graph(int paralength) {
fgh = new IntMatrix(paralength,paralength);
}//创建一个方形矩阵。
public Graph(IntMatrix para) {
fgh = new IntMatrix(para);
}//利用矩阵创建图
public Graph(Graph para) {
fgh = new IntMatrix(para.fgh);
}//利用图来进行复制。
public Graph(int[][] temp) {
fgh = new IntMatrix(temp);
}
public String toString() {
String result = "连通矩阵如下:\r\n"+fgh;
return result;
}
public boolean getConnectivity() throws Exception{//终于懂了,获取连通性的方法,分别以单个节点(M0),一个距离(M1),两个距离(M2)。。等等。。因为如果最后不连通的话,这些相加起来绝对为0(如果不懂建议看看离散数学)
//总体思路就是遍历每一种可能,发现有0的存在说明这张图不连通(这里是有向图的思路,无向图差不多)
//首先获取一个单位矩阵
IntMatrix tempMatrix = new IntMatrix(fgh.GetRows(),fgh.GetRows());//中间矩阵
IntMatrix tempfgh = IntMatrix.getIdentityMatrix(fgh.GetRows());
//接下来需要检测连通性,还需要这里的fgh,经过节点数-1次循环相加后得到最后的矩阵(为了之后的0的判断)
for(int i = 0;i<fgh.GetRows();i++) {
tempMatrix.add(tempfgh);
tempfgh = IntMatrix.Multiple(tempfgh, fgh);//多算了一次,没有影响,因为最后结果是不包含多出来的这一次的。
}
//最后的矩阵得出来了,接下来就非常简单了,直接冒泡遍历查询矩阵中是否有0的存在即可。
for(int i = 0;i<tempMatrix.GetRows();i++) {
for(int j = 0;j<tempMatrix.GetRows();j++) {
if(tempMatrix.getValue(i, j) == 0) {
return false;
}
}
}
return true;
}
//对以上的程序进行测试。。
public static void main(String[] args) {
//先测试无向图
int[][] temp = {{1,1,0,0},{0,1,1,0},{1,0,1,0},{1,0,0,1}};
Graph test = new Graph(temp);
boolean result=true;
try {
result = test.getConnectivity();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println(result);
}
}
false