图的尝试(一)(矩阵的基础运算和图的连通性检测)

一:矩阵的基础运算:

先来编写一段矩阵相乘和相加以及初始化的代码(后面附上结果图),以此为基础,开启图的学习:

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

上一篇:koa01


下一篇:javascript – 如何在我的Koa.js应用程序验收测试中使用ES2016(ES7)async / await?