package dn1124;
/**
* @author sj E-mail: 961784535@qq.com
* @version 创建时间: 2017-11-26 下午10:16:38
* 类说明: (带权有向图)邻接矩阵表示图代码实现
*/
public class Graph {
public static final int MAX_WEIGHT=-1;//表示无穷大
private int[] vertices;//顶点
private int[][] matrix;//图的节点的边
private int verticeSize;//定点的数量
public Graph(int verticeSize) {
super();
this.verticeSize = verticeSize;
this.vertices =new int[verticeSize];
this.matrix = new int[verticeSize][verticeSize];
for(int i=0;i<verticeSize;i++){
vertices[i]=i;
}
}
/**
* 计算v1到v2的权重(路径长度)
* @param v1 顶点
* @param v2 顶点
* @return
*/
public int getWeight(int v1,int v2){
int weight=matrix[v1][v2];
return weight==0 ? 0 :( weight==MAX_WEIGHT ? -1 : weight);
}
/**
* 获取所有顶点
* @return
*/
public int[] getVertices(){
return vertices;
}
/**
* 计算某个顶点的出度
* @param v
* @return
*/
public int getOutDegree(int v){
int count=0;
for(int i=0;i<matrix[v].length;i++){
if(matrix[v][i]!=0 && matrix[v][i]!=MAX_WEIGHT){
count++;
}
}
return count;
}
/**
* 计算某个顶点的入度
* @param v
* @return
*/
public int getIntDegree(int v){
int count=0;
for(int i=0;i<matrix[v].length;i++){
if(matrix[i][v]!=0 && matrix[i][v]!=MAX_WEIGHT){
count++;
}
}
return count;
}
/**
* 返回某个顶点的第一个邻接点
* @return
*/
public int getFirstNeightBor(int v){
for(int i=0;i<verticeSize;i++){
if(matrix[v][i]>0 && matrix[v][i] !=MAX_WEIGHT){
return i;
}
}
return -1;
}
/**
* 查找接点v的临界点index的下一个邻接点
* @param v 节点
* @param index 节点
* @return
*/
public int getNextNeightBor(int v,int index){
for(int i=index+1;i<verticeSize;i++){
if(matrix[v][i]>0 && matrix[v][i] !=MAX_WEIGHT){
return i;
}
}
return -1;
}
public static void main() {
//构建一个图
Graph graph=new Graph(5);
int[] a0=new int[]{0,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,6 };
int[] a1=new int[]{9,0,3,MAX_WEIGHT,MAX_WEIGHT };
int[] a2=new int[]{2,MAX_WEIGHT,0,5,MAX_WEIGHT };
int[] a3=new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,0,1 };
int[] a4=new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
graph.matrix[0]=a0;
graph.matrix[1]=a1;
graph.matrix[2]=a2;
graph.matrix[3]=a3;
graph.matrix[4]=a4;
System.out.println("v2的入度: "+graph.getIntDegree(2));
System.out.println("v2的出度: "+graph.getOutDegree(2));
System.out.println("第一个邻接点: "+graph.getFirstNeightBor(2));
System.out.println("v2关于v0的下一个邻接点: "+graph.getNextNeightBor(2,0));
}
}
单元测试里面:
public class Test {
@org.junit.Test
public void methed(){
Graph.main();
}
}
运行结果如下: